# Lifting

In integer programming, it is creating a valid inequality for the original set, given one for a lower dimensional set, by augmenting a binary variable that is absent from the original inequality. That is, suppose $LaTeX: S$ is a subset of $LaTeX: \{0,1\}^n$ and $LaTeX: a^T x \le b$ is a valid inequality for $LaTeX: S\cap \{x \in \{0,1\}^n: x_1=0\}$ (where it does not matter what $LaTeX: a_1$ is since $LaTeX: x_1=0$). Then, under certain conditions, the inequality is valid for $LaTeX: S$. The "conditions" are problem dependent, and $LaTeX: a_1$ is set as large as possible.

For example, suppose $LaTeX: x_2 + x_3 + x_4 \le 2$ is a valid inequality for $LaTeX: S$. A lifting is the strengthening, $LaTeX: 2x_1 + x_2 + x_3 + x_4 \le 2$, if it can be ascertainted that this is a valid inequality for $LaTeX: S$. The coeffiecient of $LaTeX: x_1$ ($LaTeX: 2$ in the example) is determined by considering how large $LaTeX: a_1$ can be with $LaTeX: x_1=1$. (In this case, the lifted inequality is valid if $LaTeX: x_2 + x_3 + x_4 \le 2$ is valid for $LaTeX: \{x \in S: x_1=0\}$ and if $LaTeX: x_1=1$ implies $LaTeX: x_2 = x_3 = x_4 = 0.$) The motivation for doing this arises in a branch and cut algorithm strategy. At a node in the search tree we might have a valid inequality, $LaTeX: a^Tx \le b$, when the branch had $LaTeX: x_1=0$, and we want to make it valid even if $LaTeX: x_1=1$. The inequality is valid for all

$LaTeX: a_1 \le b - \max \{a_2 x_2 + \ldots + a_n x_n : x \mbox{ feasible and } x_1 = 1\}.$