On the relative strength of split, triangle and quadrilateral cuts

DOI10.1007/s10107-009-0281-xzbMath1206.90103arXiv1701.06536MaRDI QIDQ623365

Pierre Bonami, Amitabh Basu, Margot, François, Cornuéjols, Gérard

Publication date: 14 February 2011

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1701.06536

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

Characterization of the split closure via geometric lifting, Theoretical challenges towards cutting-plane selection, On the polyhedrality of cross and quadrilateral closures, Cut generation through binarization, Approximating polyhedra with sparse inequalities, Split cuts from sparse disjunctions, On the Practical Strength of Two-Row Tableau Cuts, A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts, A note on the split rank of intersection cuts, Intersection cuts from multiple rows: a disjunctive programming approach, Can Cut-Generating Functions Be Good and Efficient?, Relaxations of mixed integer sets from lattice-free polyhedra, Approximation of Corner Polyhedra with Families of Intersection Cuts, A Probabilistic Analysis of the Strength of the Split and Triangle Closures, The triangle closure is a polyhedron, Relaxations of mixed integer sets from lattice-free polyhedra, Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra, Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case

Cites Work

• Unnamed Item
• Unnamed Item
• Chvátal closures for mixed integer programming problems
• A recursive procedure to generate all cuts for 0-1 mixed integer programs
• Worst-case comparison of valid inequalities for the TSP
• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• On the facets of mixed integer programs with two integer variables and two constraints
• Optimizing over the split closure
• Minimal Valid Inequalities for Integer Constraints
• Computing with Multi-row Gomory Cuts
• Lifting Integer Variables in Minimal Inequalities Corresponding to Lattice-Free Triangles
• Aggregation and Mixed Integer Rounding to Solve MIPs
• Solving Large-Scale Zero-One Linear Programming Problems
• On the existence of optimal solutions to integer and mixed-integer programming problems
• Inequalities from Two Rows of a Simplex Tableau
• On the MIR Closure of Polyhedra
• Intersection Cuts—A New Type of Cutting Planes for Integer Programming