Lifting Techniques For Mixed Integer Programming

This article provides a review of lifting techniques for the generation of cutting planes in mixed integer programming. After motivating the notion of lifting graphically, four key steps in the derivation of lifted inequalities are described: (i) variables fixing, (ii) derivation of seed inequalities, (iii) (re-)computation of lifting functions, and (iv) derivation of lifting coefficients. Practical considerations that are relevant to each of these steps are discussed and is emphasized the importance of superadditivity in designing efficient lifting procedures. This concluded with a description of the strength of lifted cuts. Throughout, concepts on a simple example are illustrated. Keywords: mixed integer programs; cutting planes; facet; lifting techniques; superadditive lifting