Sparsity of Lift-and-Project Cutting Planes

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

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 languageEnglish
Title of host publicationOperations Research Proceedings 2012
Subtitle of host publicationSelected Papers of the International Annual Conference of the German Operations Research Society (GOR), Leibniz University of Hannover, Germany, September 5-7, 2012
EditorsStefan Helber, Michael Breitner, Daniel Rösch, Cornelia Schön, Johann-Matthias Graf von der Schulenburg, Philipp Sibbertsen, Marc Steinbach, Stefan Weber, Anja Wolter
PublisherSpringer International Publishing AG
Pages9-14
Number of pages6
ISBN (Electronic)978-3-319-00795-3
ISBN (Print)978-3-319-00794-6
DOIs
Publication statusPublished - 2012
Externally publishedYes

Fingerprint

Dive into the research topics of 'Sparsity of Lift-and-Project Cutting Planes'. Together they form a unique fingerprint.

Cite this