down lifting of variable coefficients for cover inequalities

Question

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?

Answer 1

Generally, the purpose of lifting is to obtain a strong inequality in a higher dimensional space than the original inequality. A cover inequality is only in very rare cases a facet defining inequality for the knapsack polytope. Even the extended cover inequalities define facets in only rare cases (see Proposition 2.3, section II.2 of Nemhauser and Wolsey).

The general theory is as follows: Suppose that $S\subseteq \{0,1\}^n$ and $S^\delta=S\cap\{x\in\{0,1\}^n:x_1=\delta\}$ for $\delta\in\{0,1\}$. Furthermore, assume that \begin{equation} \sum_{j=2}^n\pi_jx_j\leq \pi_0 \end{equation} is a facet defining inequality for $\text{conv}(S^0)$, then if $S^1\neq \emptyset$ and $\alpha_1=\pi_0-\max\{\sum_{j=2}^n\pi_jx_j:x\in S^1\}$ it can be shown that \begin{equation} \alpha_1x_1+\sum_{j=2}^n\pi_jx_j\leq \pi_0 \end{equation} is facet defining for $\text{conv}(S)$. If $\sum_{j=2}^n\pi_jx_j\leq \pi_0$ on the other hand is a facet defining for $\text{conv}(S^1)$ and $S^0\neq\emptyset$ then \begin{equation} \gamma_1x_1+\sum_{j=2}^n\pi_jx_j\leq \pi_0+\gamma_1 \end{equation} is a facet defining inequality for $\text{conv}(S)$ if $\gamma_1=\pi_0-\max\{ \sum_{j=2}^n\pi_jx_j:x\in S^0\}$ (these claims are proven in Proposition 1.1. and 1.2. in section II.2 of Nemhauser and Wolsey). Due to these results, if we can prove a given inequality is facet defining for a restricted version of the original polytope ("restricted polytope" here means the polytope in a lower dimensional space obtained by fixing some variables to either zero or one), then up- and down-lifting can be used sequentially to generate a facet defining inequality for the original high-dimensional polytope.

The last result needed is stated in Corollary 2.4 in section II.2. of Nemhauser and Wolsey: If $C\subseteq\{1,...,n\}$ is a minimal cover for the knapsack $S=\{x\in\{0,1\}:\sum_{j=1}^n a_jx_j\leq b\}$ and $(C_1,C_2)$ is a partition of $C$, with $C_1\neq \emptyset$, then $\sum_{j\in C_1}x_1\leq \vert C_1\vert-1$ is a facet defining inequality for $\text{conv}(S(C_1,C_2))$, where \begin{equation} S(C_1,C_2)=\{ x\in\{0,1\}^{\vert C_1\vert}: \sum_{j\in C_1}a_jx_j\leq b-\sum_{j\in C_2}a_j \} \end{equation}

With this result, we can sequentially apply down-lifting of the variables in $C_2$ and up-lifting of the variables in $\{1,...,n\}\setminus C$ in order to get a facet defining inequality for $\text{conv}(\{x\in\{0,1\}:\sum_{j=1}^n a_jx_j\leq b\})$.