Given a cover inequality of the form: \begin{equation} \sum_{j\in C}x_j \leq |C|-1 \end{equation}
A lifted version of this inequality takes the following form: \begin{equation} \sum_{j\in C}x_j+\sum_{j\in N\setminus C}\alpha_jx_j \leq |C|-1 \end{equation}
As long as $\alpha_j\geq 0$, $\forall j\in N\setminus C$, it follows that the lifted version of this inequality is stronger than the original cover inequality, because we add more arguments to the LHS without changing the RHS. The $\alpha_j$ coefficients can be obtained through a sequantial procedure.
This particular form of lifting is in some papers referred to as 'uplifting'. Equivalently, there exists another form of lifting known as 'down lifting'. For a given $D\subset N$, $N\cap C = \emptyset$, a downlifted version of the cover inequality:
\begin{equation} \sum_{j\in C\setminus D}x_j+\sum_{j\in D}\beta_jx_j \leq |C|+\sum_{j\in D}\beta_j-1 \end{equation}
In contrast to the uplifted version, in the downlifted version we modify the RHS. As such, it is not obvious to me:
- why/when is this down lifted inequality stronger than the original cover inequality?
For a given $j\in D$, when $x_j=1$ the $\beta_j$ terms of the LHS and RHS cancel each other out and we obtain the orignal cover inequality. However, when $x_j=0$, the RHS remains larger and we obtain an inequality that seems weaker?
- when would you apply down lifting?