Lifted inequalities for 0-1 mixed integer programming: Basic theory and algorithms (Q1424281)

In order to describe the facets of a high dimensional polytope, an effective approach consists of reducing the number of variables (by fixing some of them at specified values), hoping to obtain a polytope for which at least one nontrivial inequality is obtained. The idea of lifting, introduced by \textit{R. E. Gomory} [Linear Algebra Appl. 2, 451-558 (1969; Zbl 0184.23103)], is to use such inequalities to subsequently generate facets of higher dimensional polytopes. The paper under review develops theory and algorithms for the lifting of continuous variables for the mixed 0-1 knapsack polytope \[ PS=\text{conv} \left \{ \, (x,y) \in \{0,1 \}^m \times [0,1]^n : \sum _{j=1}^m a_jx_j+\sum _{i=1}^n b_i y_i\leq d\,\right \}, \] where \(m>0\), \(n>0\), \(a_j\), \(b_i\), \(d\) are integers. Strong robust cuts for 0-1 mixed integer programming are derived by exploiting the boundedness of and the presence of more than one continuous variable in \(PS\). A first original result implies that it is almost always sufficient to fix continuous variables at 0 or 1. Next it is proved that the lifting coefficients of the continuous variables fixed at 0 are almost always zero. Moreover, it is possible to completely specify the lifting coefficients for variables lifted from 0. A similar study of the lifting from 1, although much more difficult, leads to a pseudo-polynomial algorithm performing this task.