Two new reformulation convexification based hierarchies for 0-1 MIPs (Q1748458): Difference between revisions

Summary: First, we introduce two new reformulation convexification based hierarchies called RTC and RSC for which the rank \(d\) continuous relaxations are denoted by \(\widehat{P}_{\mathtt{ {RTC}}}^d\) and \(\widehat{P}_{\mathtt{ {RSC}}}^d\), respectively. These two hierarchies are obtained using two different convexification schemes: \textit{term convexification} in the case of the \texttt{RTC} hierarchy and \textit{standard convexification} in the case of the \texttt{RSC} hierarchy. Secondly, we compare the \textit{strength} of these two hierarchies. We will prove that (i) the hierarchy \texttt{RTC} is \textit{equivalent} to the \texttt{RLT} hierarchy of Sherali-Adams, (ii) the hierarchy \texttt{RTC} dominates the hierarchy \texttt{RSC}, and (iii) the hierarchy \texttt{RSC} is dominated by the Lift-and-Project hierarchy. Thirdly, for every rank \(d\), we will prove that \(\mathrm{conv} \left(\mathcal{T}^d \cap \mathcal{E}_t^d\right) \subseteq \widehat{P}_{\mathtt{ {RTC}}}^d \subseteq \mathcal{T}^d\) and \(\mathrm{conv} \left(\mathcal{S}^d \ cap \mathcal{E}_s^d\right) \subseteq \widehat{P}_{\mathtt{ {RSC}}}^d \subseteq \mathcal{S}^d\) where the sets \(\mathcal{T}^d\) and \(\mathcal{S}^d\) are convex, while \(\mathcal{E}_t^d\) and \(\mathcal{E}_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 the \texttt{RLT} relaxations. Finally, we will discuss weak version of both \texttt{RTC} and \texttt{RSC} hierarchies and we will emphasize some connections between them.