Two New Reformulation Convexification Based Hierarchies for 0-1 MIPs

摘要

First, we introduce two new reformulation convexification based hierarchies calledRTCandRSCfor which the rankdcontinuous relaxations are denoted byP^RTCdandP^RSCd, respectively. These two hierarchies are obtained using two different convexification schemes:term convexificationin the case of theRTChierarchy andstandard convexificationin the case of theRSChierarchy. Secondly, we compare thestrengthof these two hierarchies. We will prove that (i) the hierarchyRTCisequivalentto theRLThierarchy of Sherali-Adams, (ii) the hierarchyRTCdominates the hierarchyRSC, and (iii) the hierarchyRSCis dominated by the Lift-and-Project hierarchy. Thirdly, for every rankd, we will prove thatconvTd∩Etd⊆P^RTCd⊆TdandconvSd∩Esd⊆P^RSCd⊆Sdwhere the setsTdandSdare convex, whileEtdandEsdare 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 theRLTrelaxations. Finally, we will discuss weak version of bothRTCandRSChierarchies and we will emphasize some connections between them.