Abstract
It is well-known that sparsity (i.e. having only a few nonzero coefficients) is a desirable property for cutting planes in mixed-integer programming. We show that on the MIPLIB 2003 problem instance set, using only 10 very dense cutting planes (compared to thousands of constraints in a model), leads to a run time increase of 25 % on average for the LP-solver. We introduce the concept of dual sparsity (a property of the row-multipliers of the cut) and show a strong correlation between dual and primal (the usual) sparsity. Lift-and-project cuts crucially depend on the choice of a so-called normalization, of which we compared several known ones with respect to their actual and possible sparsity. Then a new normalization is tested that improves the dual (and hence the primal) sparsity of the generated cuts.
Original language | English |
---|---|
Title of host publication | Operations Research Proceedings 2012 |
Subtitle of host publication | Selected Papers of the International Annual Conference of the German Operations Research Society (GOR), Leibniz University of Hannover, Germany, September 5-7, 2012 |
Editors | Stefan Helber, Michael Breitner, Daniel Rösch, Cornelia Schön, Johann-Matthias Graf von der Schulenburg, Philipp Sibbertsen, Marc Steinbach, Stefan Weber, Anja Wolter |
Publisher | Springer |
Pages | 9-14 |
Number of pages | 6 |
ISBN (Electronic) | 978-3-319-00795-3 |
ISBN (Print) | 978-3-319-00794-6 |
DOIs | |
Publication status | Published - 2012 |
Externally published | Yes |