On the practical strength of two-row tableau cuts
(2013) INFORMS Journal on Computing — Vol. 26, n° 2, p. 222-237 (2013)
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- Following the flurry of recent theoretical work on cutting planes from two-row mixed integer group relax-cuts based on lattice-free triangles having more than one integer point on one side. A heuristic procedure to generate such triangles are tightened by lifting. To test the effectiveness of triangle cuts, we compare the gap closed using Gomory mixed integer cuts for one round, the gap closed in one round using all the triangle cuts generated by our heuristic, and the gap closed by a small number of two-row split cuts. Our tests are carried out on randomly generated instances designed to represent different problem features by varying the number of integer nonbasic variables, bounds, nonnegativity constraints, and density, as well as on the classical MIPLIB instances. The outcome of this computational analysis is some insight into key characteristics of MIP instances whose presence makes two-row triangle cuts computationally effective. In particular, it appears to be necessary that the tableau row pairs are dense, and more subjectively that the nonbasic continuous variables are ``important". Unfortunately these characteristics seem to be rarely present among real-life instances, and more specifically the tableau rows of the MIPLIB instances are far from dense.
- Affiliations
Citations
Dey, S., Lodi, A., Tramontani, A., & Wolsey, L. (2013). On the practical strength of two-row tableau cuts. INFORMS Journal on Computing, 26(2), 222-237. https://doi.org/10.1287/ijoc.2013.0559 (Original work published 2013)