1
$\begingroup$

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?
$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – Sune
    May 8 at 11:01

1 Answer 1

1
$\begingroup$

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\})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.