A note on the split rank of intersection cuts
The author analyzes mixed integer programs with \(m\) integer variables, \(n\) nonnegative continuous variables and a restriction vector \(f\) with at least one non-integer component. In a branch-and-cut framework split cuts -- introduced by Egon Balas more than 35 years ago by using disjunctions for integer-valued inequalities -- have shown to be of certain value; by adding all possible split cuts to the linear programming relaxation \(M\) one gets the first split closure \(M^1\), which was shown to be a polyhedron. Applying the split closure procedure to the resulting set iteratively again yields the second split closure \(M^2,\dots,M^t,\dots\) The split rank of a valid inequality for the convex hull of the mixed integer set of solutions is defined as the smallest integer \(t\) , such that the inequality is valid for \(M^t\) (or can be infinite shown by simple examples where the facet-defining inequality cannot be obtained using split cuts). This rank indicates how difficult it is to obtain an inequality using split cuts. The main result of the paper shows a lower bound on the split rank of the class of intersection cuts (a general class due to Balas too): after having constructed a polyhedral subset of the lattice-free convex set \(P\), which contains the vector \(f\) in its interior, one looks for a number \(k\) of integer points that lie on different faces of \(P\); then \(\log_2 (k)\) is a lower bound for the rank. This result can be specialized for \(n\)-row mixing inequalities yielding a lower bound of \(\log_2(n+1)\). The proofs are based mainly on geometric arguments.
- A constructive characterization of the split closure of a mixed integer linear program
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- A recursive procedure to generate all cuts for 0-1 mixed integer programs
- Chvátal closures for mixed integer programming problems
- Computing with Multi-row Gomory Cuts
- Cook, Kannan and Schrijver's example revisited
- Cutting planes in integer and mixed integer programming
- Disjunctive Programming
- Elementary closures for integer programs.
- Gomory cuts revisited
- scientific article; zbMATH DE number 3156817 (Why is no real title available?)
- scientific article; zbMATH DE number 193411 (Why is no real title available?)
- scientific article; zbMATH DE number 3545380 (Why is no real title available?)
- Inequalities from Two Rows of a Simplex Tableau
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- Lifting Integer Variables in Minimal Inequalities Corresponding to Lattice-Free Triangles
- Minimal valid inequalities for integer constraints
- Mixing mixed-integer inequalities
- On degenerate multi-row Gomory cuts
- On mixing inequalities: rank, closure, and cutting-plane proofs
- On the facets of mixed integer programs with two integer variables and two constraints
- On the MIR Closure of Polyhedra
- On the rank of mixed 0,1 polyhedra.
- On the relative strength of split, triangle and quadrilateral cuts
- Optimizing over the split closure
- Polyhedra for lot-sizing with Wagner-Whitin costs
- Production Planning by Mixed Integer Programming
- Progress in computational mixed integer programming -- a look back from the other side of the tipping point
- Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition
- Some continuous functions related to corner polyhedra, II
- Split closure and intersection cuts
- Strengthening cuts for mixed integer programs
- Tight formulations for some simple mixed integer programs and convex objective integer programs
- Theoretical challenges towards cutting-plane selection
- Intersection cuts for convex mixed integer programs from translated cones
- Split closure and intersection cuts
- Mixed \(n\)-step MIR inequalities: facets for the \(n\)-mixing set
- On the facet defining inequalities of the mixed-integer bilinear covering set
- Disjunctive programming and relaxations of polyhedra
- Optimizing over the split closure
- Two-halfspace closure
- Split rank of triangle and quadrilateral inequalities
- Intersection cuts with infinite Split rank
- On the rank of disjunctive cuts
- scientific article; zbMATH DE number 5943737 (Why is no real title available?)
- Characterization of the split closure via geometric lifting
- On an analysis of the strength of mixed-integer cutting planes from multiple simplex tableau rows
- On mixing inequalities: rank, closure, and cutting-plane proofs
- Practical strategies for generating rank-1 split cuts in mixed-integer linear programming
- Composite lifting of group inequalities and an application to two-row mixing inequalities
- scientific article; zbMATH DE number 1757948 (Why is no real title available?)
- 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?)
- Cutting planes from extended LP formulations
- Multirow Intersection Cuts Based on the Infinity Norm
- Nonunique lifting of integer variables in minimal inequalities
- Relaxations of mixed integer sets from lattice-free polyhedra
- Relaxations of mixed integer sets from lattice-free polyhedra
- On polytopes with linear rank with respect to generalizations of the split closure
- Cook, Kannan and Schrijver's example revisited
This page was built for publication: A note on the split rank of intersection cuts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q647399)
