Mixed Integer Rounding Cuts and Master Group Polyhedra
Sanjeeb Dash · NATO science for peace and security series. D, Information and communication security · 2011
We survey recent research on mixed-integer rounding (MIR) inequalities and a generalization, namely the two-step MIR inequalities defined by Dash and Günlük (2006). We discuss the master cyclic group polyhedron of Gomory (1969) and discuss how other subadditive inequalities, similar to MIR inequalities, can be derived from this polyhedron. Recent numerical experiments have shed much light on the strength of MIR inequalities and the closely related Gomory mixed-integer cuts, especially for the MIP instances in the MIPLIB 3.0 library, and we discuss these experiments and their outcomes. Balas and Saxena (2007), and independently, Dash, Günlük and Lodi (2007), study the strength of the MIR closure of MIPLIB instances, and we explain their approach and results here. We also give a short proof of the well-known fact that the MIR closure of a polyhedral set is a polyhedron. Finally, we conclude with a survey of the complexity of cutting-plane proofs which use MIR inequalities.