# Lifting

### From Glossary

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 is a subset of
and is a valid inequality for
(where it does not matter what
is since ). Then,
under certain conditions, the inequality is valid for . The
"conditions" are problem dependent, and is set as large as
possible.

For example, suppose is a
valid inequality for . A *lifting* is the strengthening,
, if it can be ascertainted that
this is a valid inequality for . The coeffiecient of
( in the example) is determined by considering how large can be
with . (In this case, the lifted inequality is valid if
is valid for and if
implies ) 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, , when the branch had
, and we want to make it valid even if . The inequality
is valid for all