Two New Reformulation Convexification Based Hierarchies for 0-1 MIPs. (29th November 2015)

• Record Type: Journal Article
• Authors: Ouzia, Hacene
• Other Names: Liao Ching-Jong Academic Editor.
• Is Part Of: Advances in operations research. Volume 2015(2015)
• Publication Date: 2015-11-29
• Subjects: Operations research -- Periodicals; Operations research; Periodicals; 003
• DOI: 10.1155/2015/784817
• Languages: English
• ISSNs: 1687-9147

Abstract

Abstract : First, we introduce two new reformulation convexification based hierarchies calledRTC andRSC for which the rankd continuous relaxations are denoted byP ^ R T C d andP ^ R S C d, respectively. These two hierarchies are obtained using two different convexification schemes: term convexification in the case of theRTC hierarchy and standard convexification in the case of theRSC hierarchy. Secondly, we compare the strength of these two hierarchies. We will prove that (i) the hierarchyRTC is equivalent to theRLT hierarchy of Sherali-Adams, (ii) the hierarchyRTC dominates the hierarchyRSC, and (iii) the hierarchyRSC is dominated by the Lift-and-Project hierarchy. Thirdly, for every rankd, we will prove thatconv T d ∩ E t d ⊆ P ^ R T C d ⊆ T d andconv S d ∩ E s d ⊆ P ^ R S C d ⊆ S d where the setsT d andS d are convex, whileE t d andE s d 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 theRLT relaxations. Finally, we will discuss weak version of bothRTC andRSC hierarchies and we will emphasize some connections between them.