Lifting

From Glossary

Jump to: navigation, search


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


Views
Personal tools