Split rank of triangle and quadrilateral inequalities

DOI10.1287/MOOR.1110.0496zbMATH Open1242.90127arXiv0906.0887OpenAlexW2157487045MaRDI QIDQ2884282FDOQ2884282

Authors: Quentin Louveaux, Santanu S. Dey 

Publication date: 24 May 2012

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

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.

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

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

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)

Cited In (12)

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

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)