Split rank of triangle and quadrilateral inequalities

DOI10.1287/MOOR.1110.0496MaRDI QIDQ2884282zbMATH OpenOpenAlexFDO

Authors Quentin Louveaux, Santanu S. Dey

Publication date 24 May 2012

Published in Mathematics of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

mixed-integer programmingsplit rankmulti-row cutting planes

Mathematics Subject Classification ID

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

Abstract: A simple relaxation of two rows of a simplex tableau is a mixed integer set consisting of two equations with two free integer variables and non-negative continuous variables. Recently Andersen, Louveaux, Weismantel and Wolsey (2007) and Cornuejols and Margot (2008) showed that the facet-defining inequalities of this set are either split cuts or intersection cuts obtained from lattice-free triangles and quadrilaterals. Through a result by Cook, Kannan and Schrijver (1990), it is known that one particular class of facet-defining triangle inequality does not have a finite split rank. In this paper, we show that all other facet-defining triangle and quadrilateral inequalities have a finite split-rank. The proof is constructive and given a facet-defining triangle or quadrilateral inequality we present an explicit sequence of split inequalities that can be used to generate it.

Recommendations

• On the relative strength of split, triangle and quadrilateral cuts
• On the relative strength of split, triangle and quadrilateral cuts
• A note on the split rank of intersection cuts
• A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts
• On the polyhedrality of cross and quadrilateral closures

Cited in

(12)

• An algorithm for the separation of two-row cuts
• Binary extended formulations of polyhedral mixed-integer sets
• The triangle closure is a polyhedron
• The strength of multi-row models
• Intersection cuts for single row corner relaxations
• Intersection cuts with infinite Split rank
• Theoretical challenges towards cutting-plane selection
• Relaxations of mixed integer sets from lattice-free polyhedra
• Relaxations of mixed integer sets from lattice-free polyhedra
• The (not so) trivial lifting in two dimensions
• On the facet defining inequalities of the mixed-integer bilinear covering set
• Lower Bounds on the Lattice-Free Rank for Packing and Covering Integer Programs

This page was built for publication: Split rank of triangle and quadrilateral inequalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2884282)