Valid inequalities for mips and group polyhedra from approximate liftings (Q1016121)

The paper presents a new simple and constructive approximate lifting scheme for the generation of cuts for mixed-integer linear programs. The approach allows the generation of strong inequalities for the group problem. First a scheme for obtaining valid inequalities for a mixed integer problem with just one constraint is described. Here a approximate superadditive lifting of the integer variables is followed by an approximate superlinear lifting of the real variables. The relations between this lifting approach and Johnson's superadditive theory of valid inequalities for MIPs is discussed as well as the relation to Gomory's subadditive characterization of the facets for the group problem. Moreover, a family of piecewise linear approximate lifting functions is introduced and it is discussed under which conditions they are superadditive. Several classes of known cutting planes and a new class of cuts are obtained by analyzing the underlying parameterized polyhedron. Moreover, the computational potential of the new approach is outlined.