A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts
From MaRDI portal
Publication:433114
DOI10.1016/J.ORL.2011.04.005zbMATH Open1242.90126arXiv1009.5253OpenAlexW1993493269WikidataQ57568139 ScholiaQ57568139MaRDI QIDQ433114FDOQ433114
Authors: Alberto Del Pia, Christian Wagner, Robert Weismantel 
Publication date: 13 July 2012
Published in: Operations Research Letters (Search for Journal in Brave)
Abstract: We consider mixed integer linear sets defined by two equations involving two integer variables and any number of non-negative continuous variables. The non-trivial valid inequalities of such sets can be classified into split, type 1, type 2, type 3, and quadrilateral inequalities. We use a strength measure of Goemans to analyze the benefit from adding a non-split inequality on top of the split closure. Applying a probabilistic model, we show that the importance of a type 2 inequality decreases with decreasing lattice width, on average. Our results suggest that this is also true for type 3 and quadrilateral inequalities.
Full work available at URL: https://arxiv.org/abs/1009.5253
Recommendations
- On the relative strength of split, triangle and quadrilateral cuts
- On the relative strength of split, triangle and quadrilateral cuts
- A probabilistic comparison of split and type 1 triangle cuts for two-row mixed-integer programs
- On the relative strength of families of intersection cuts arising from pairs of tableau constraints in mixed integer programs
- A probabilistic analysis of the strength of the split and triangle closures
Cites Work
- Two row mixed-integer cuts via lifting
- Inequalities from Two Rows of a Simplex Tableau
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- On the existence of optimal solutions to integer and mixed-integer programming problems
- Worst-case comparison of valid inequalities for the TSP
- Inequalities for the lattice width of lattice-free convex sets in the plane
- Blowing up convex sets in the plane
- Optimizing over the split closure
- On the relative strength of split, triangle and quadrilateral cuts
- Chvátal closures for mixed integer programming problems
- Title not available (Why is that?)
- A probabilistic comparison of split and type 1 triangle cuts for two-row mixed-integer programs
- On an analysis of the strength of mixed-integer cutting planes from multiple simplex tableau rows
- Zero-coefficient cuts
Cited In (11)
- On the relative strength of families of intersection cuts arising from pairs of tableau constraints in mixed integer programs
- Can Cut-Generating Functions Be Good and Efficient?
- Theoretical challenges towards cutting-plane selection
- Combinatorial optimization: the interplay of graph theory, linear and integer programming illustrated on network flow
- On the relative strength of split, triangle and quadrilateral cuts
- On an analysis of the strength of mixed-integer cutting planes from multiple simplex tableau rows
- A probabilistic comparison of split and type 1 triangle cuts for two-row mixed-integer programs
- Relaxations of mixed integer sets from lattice-free polyhedra
- Relaxations of mixed integer sets from lattice-free polyhedra
- A probabilistic analysis of the strength of the split and triangle closures
- Split rank of triangle and quadrilateral inequalities
This page was built for publication: A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q433114)
