Intersection cuts with infinite Split rank

DOI10.1287/MOOR.1110.0522MaRDI QIDQ2884303zbMATH OpenOpenAlexFDO

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

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/1701.06606

zbMATH Keywords

cutting planesmixed-integer programmingsplit rank

Mathematics Subject Classification ID

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

Abstract: We consider mixed integer linear programs where free integer variables are expressed in terms of nonnegative continuous variables. When this model only has two integer variables, Dey and Louveaux characterized the intersection cuts that have infinite split rank. We show that, for any number of integer variables, the split rank of an intersection cut generated from a bounded convex set $P$ is finite if and only if the integer points on the boundary of $P$ satisfy a certain "2-hyperplane property". The Dey-Louveaux characterization is a consequence of this more general result.

Recommendations

• A note on the split rank of intersection cuts
• Lower Bounds on the Lattice-Free Rank for Packing and Covering Integer Programs
• scientific article; zbMATH DE number 2086918
• Split rank of triangle and quadrilateral inequalities
• On the rank of disjunctive cuts

Cited in

(17)

• Theoretical challenges towards cutting-plane selection
• On the relative strength of different generalizations of split cuts
• Intersection cuts for convex mixed integer programs from translated cones
• Split closure and intersection cuts
• Disjunctive programming and relaxations of polyhedra
• On the rank of disjunctive cuts
• Characterization of the split closure via geometric lifting
• Can cut-generating functions be good and efficient?
• Lower Bounds on the Lattice-Free Rank for Packing and Covering Integer Programs
• scientific article; zbMATH DE number 2086918 (Why is no real title available?)
• Multirow Intersection Cuts Based on the Infinity Norm
• Combinatorial optimization: the interplay of graph theory, linear and integer programming illustrated on network flow
• Reverse split rank
• Relaxations of mixed integer sets from lattice-free polyhedra
• Relaxations of mixed integer sets from lattice-free polyhedra
• A note on the split rank of intersection cuts
• Reverse split rank

This page was built for publication: Intersection cuts with infinite Split rank

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