A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts
From MaRDI portal
(Redirected from Publication:433114)
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.
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
- scientific article; zbMATH DE number 4119933 (Why is no real title available?)
- A probabilistic comparison of split and type 1 triangle cuts for two-row mixed-integer programs
- Blowing up convex sets in the plane
- Chvátal closures for mixed integer programming problems
- Inequalities for the lattice width of lattice-free convex sets in the plane
- Inequalities from Two Rows of a Simplex Tableau
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- On an analysis of the strength of mixed-integer cutting planes from multiple simplex tableau rows
- On the existence of optimal solutions to integer and mixed-integer programming problems
- On the relative strength of split, triangle and quadrilateral cuts
- Optimizing over the split closure
- Two row mixed-integer cuts via lifting
- Worst-case comparison of valid inequalities for the TSP
- Zero-coefficient cuts
Cited in
(11)- A probabilistic comparison of split and type 1 triangle cuts for two-row mixed-integer programs
- A probabilistic analysis of the strength of the split and triangle closures
- On the relative strength of families of intersection cuts arising from pairs of tableau constraints in mixed integer programs
- Combinatorial optimization: the interplay of graph theory, linear and integer programming illustrated on network flow
- Can cut-generating functions be good and efficient?
- Split rank of triangle and quadrilateral inequalities
- Theoretical challenges towards cutting-plane selection
- Relaxations of mixed integer sets from lattice-free polyhedra
- Relaxations of mixed integer sets from lattice-free polyhedra
- On an analysis of the strength of mixed-integer cutting planes from multiple simplex tableau rows
- On the relative strength of split, triangle and quadrilateral cuts
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)
