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.
|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|
|Number of pages||6|
|Publication status||Published - 2012|