Two New Reformulation Convexification Based Hierarchies for 0-1 MIPs

Hacene Ouzia

Advances in Operations Research, 2015, vol. 2015, 1-13

Abstract:

First, we introduce two new reformulation convexification based hierarchies called RTC and RSC for which the rank continuous relaxations are denoted by and , respectively. These two hierarchies are obtained using two different convexification schemes: term convexification in the case of the RTC hierarchy and standard convexification in the case of the RSC hierarchy. Secondly, we compare the strength of these two hierarchies. We will prove that (i) the hierarchy RTC is equivalent to the RLT hierarchy of Sherali-Adams, (ii) the hierarchy RTC dominates the hierarchy RSC , and (iii) the hierarchy RSC is dominated by the Lift-and-Project hierarchy. Thirdly, for every rank , we will prove that and where the sets and are convex, while and are two nonconvex sets with empty interior (all these sets depend on the convexification step). The first inclusions allow, in some cases, an explicit characterization (in the space of the original variables) of the RLT relaxations. Finally, we will discuss weak version of both RTC and RSC hierarchies and we will emphasize some connections between them.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/AOR/2015/784817.pdf (application/pdf)
http://downloads.hindawi.com/journals/AOR/2015/784817.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlaor:784817

DOI: 10.1155/2015/784817

Access Statistics for this article

More articles in Advances in Operations Research from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().