Two row mixed-integer cuts via lifting (Q2638372)

This article presents the characteristics of the lifting functions which provide the coefficients of the integer variables which define valid inequalities, or cuts, obtained from two rows of a general simplex tableau in a mixed-integer programming context. The paper begins with an overview of mixed-integer programs and cutting planes such as the facet-defining Gomory cuts. The authors expand this approach to derive strong cuts from two rows at a time. The second section contains the necessary background to mixed-integer group relaxations and lattice-free convex sets in two dimensions. This is followed by a description of the proposed approach to generate the cutting planes based on two rows of the tableau. This includes the various steps and an illustrative example of the proposed algorithm. The next four sections concentrate on the proof of the properties of the algorithm where a large number of relevant theorems are presented. This novel article concludes with a summary of the main findings, suggestions for future research and a list of relevant references.