# down lifting of variable coefficients for cover inequalities

Given a cover inequality of the form: $$$$\sum_{j\in C}x_j \leq |C|-1$$$$

A lifted version of this inequality takes the following form: $$$$\sum_{j\in C}x_j+\sum_{j\in N\setminus C}\alpha_jx_j \leq |C|-1$$$$

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:

$$$$\sum_{j\in C\setminus D}x_j+\sum_{j\in D}\beta_jx_j \leq |C|+\sum_{j\in D}\beta_j-1$$$$

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?
• See section II.2 ("Valid inequalities for the 0-1 knapsack polytope") of Nemhauser and Wolsey, Integer and combinatorial optimization. This section describes it quite well. Hoffman and Padberg recommend to set $D=\{i\in C:x_i^*=1\}$. Then first up-lift variables with $x_i^*>0$, where $i\not \in C$ (this strengthens the inequality), next down-lift variables in $D$ (makes room for more variables with positive coefficients), finally up-lift variables with $x^*_j=0$ where $j\not\in C$ (strengthen again).
– Sune
May 8 at 11:01

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 $$$$\sum_{j=2}^n\pi_jx_j\leq \pi_0$$$$ 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 $$$$\alpha_1x_1+\sum_{j=2}^n\pi_jx_j\leq \pi_0$$$$ 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 $$$$\gamma_1x_1+\sum_{j=2}^n\pi_jx_j\leq \pi_0+\gamma_1$$$$ 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 $$$$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 \}$$$$
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\})$$.