Sparsity of Lift-and-Project Cutting Planes

Matthias Walter

doi:10.1007/978-3-319-00795-3_2

Sparsity of Lift-and-Project Cutting Planes

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-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 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	https://doi.org/10.1007/978-3-319-00795-3_2
Publication status	Published - 2012
Externally published	Yes

Access to Document

10.1007/978-3-319-00795-3_2

Cite this

Walter, M. (2012). Sparsity of Lift-and-Project Cutting Planes. In S. Helber, M. Breitner, D. Rösch, C. Schön, J-M. Graf von der Schulenburg, P. Sibbertsen, M. Steinbach, S. Weber, & A. Wolter (Eds.), Operations Research Proceedings 2012: Selected Papers of the International Annual Conference of the German Operations Research Society (GOR), Leibniz University of Hannover, Germany, September 5-7, 2012 (pp. 9-14). Springer. https://doi.org/10.1007/978-3-319-00795-3_2

Walter, Matthias. / Sparsity of Lift-and-Project Cutting Planes. Operations Research Proceedings 2012: Selected Papers of the International Annual Conference of the German Operations Research Society (GOR), Leibniz University of Hannover, Germany, September 5-7, 2012. editor / Stefan Helber ; Michael Breitner ; Daniel Rösch ; Cornelia Schön ; Johann-Matthias Graf von der Schulenburg ; Philipp Sibbertsen ; Marc Steinbach ; Stefan Weber ; Anja Wolter. Springer, 2012. pp. 9-14

@inbook{4d19bbca8cf44e68861ec503e8e453c1,

title = "Sparsity of Lift-and-Project Cutting Planes",

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.",

author = "Matthias Walter",

year = "2012",

doi = "10.1007/978-3-319-00795-3_2",

language = "English",

isbn = "978-3-319-00794-6",

pages = "9--14",

editor = "Stefan Helber and Michael Breitner and Daniel R{\"o}sch and Cornelia Sch{\"o}n and {Graf von der Schulenburg}, Johann-Matthias and Philipp Sibbertsen and Marc Steinbach and Stefan Weber and Anja Wolter",

booktitle = "Operations Research Proceedings 2012",

publisher = "Springer",

address = "Netherlands",

}

Walter, M 2012, Sparsity of Lift-and-Project Cutting Planes. in S Helber, M Breitner, D Rösch, C Schön, J-M Graf von der Schulenburg, P Sibbertsen, M Steinbach, S Weber & A Wolter (eds), Operations Research Proceedings 2012: Selected Papers of the International Annual Conference of the German Operations Research Society (GOR), Leibniz University of Hannover, Germany, September 5-7, 2012. Springer, pp. 9-14. https://doi.org/10.1007/978-3-319-00795-3_2

Sparsity of Lift-and-Project Cutting Planes. / Walter, Matthias.

Operations Research Proceedings 2012: Selected Papers of the International Annual Conference of the German Operations Research Society (GOR), Leibniz University of Hannover, Germany, September 5-7, 2012. ed. / Stefan Helber; Michael Breitner; Daniel Rösch; Cornelia Schön; Johann-Matthias Graf von der Schulenburg; Philipp Sibbertsen; Marc Steinbach; Stefan Weber; Anja Wolter. Springer, 2012. p. 9-14.

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic › peer-review

TY - CHAP

T1 - Sparsity of Lift-and-Project Cutting Planes

AU - Walter, Matthias

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-00795-3_2

DO - 10.1007/978-3-319-00795-3_2

M3 - Chapter

SN - 978-3-319-00794-6

SP - 9

EP - 14

BT - Operations Research Proceedings 2012

A2 - Helber, Stefan

A2 - Breitner, Michael

A2 - Rösch, Daniel

A2 - Schön, Cornelia

A2 - Graf von der Schulenburg, Johann-Matthias

A2 - Sibbertsen, Philipp

A2 - Steinbach, Marc

A2 - Weber, Stefan

A2 - Wolter, Anja

PB - Springer

ER -

Walter M. Sparsity of Lift-and-Project Cutting Planes. In Helber S, Breitner M, Rösch D, Schön C, Graf von der Schulenburg J-M, Sibbertsen P, Steinbach M, Weber S, Wolter A, editors, Operations Research Proceedings 2012: Selected Papers of the International Annual Conference of the German Operations Research Society (GOR), Leibniz University of Hannover, Germany, September 5-7, 2012. Springer. 2012. p. 9-14 doi: 10.1007/978-3-319-00795-3_2

Sparsity of Lift-and-Project Cutting Planes

Abstract

Access to Document

Fingerprint

Cite this