Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming
From MaRDI portal
Publication:2248762
This paper proves that for every integer \(n\) there exists a positive integer \(t\) such that every facet-defining inequality of the convex hull of a mixed integer polyhedral set with \(n\) integer variables is a \(t\)-branch split cut. This result is used to derive a finite cutting-plane algorithm to solve mixed integer programs. The authors also show that the minimum value of \(t\) for which the result holds grows exponentially with \(n\).
Recommendations
Cites work
- A disjunctive cutting plane procedure for general mixed-integer linear programs
- A hierarchy of relaxations leading to the convex hull representation for general discrete optimization problems
- Blowing up convex sets in the plane
- Chvátal closures for mixed integer programming problems
- Cook, Kannan and Schrijver's example revisited
- Covering minima and lattice-point-free convex bodies
- Disjunctive Programming
- Distances between non-symmetric convex bodies and the \(MM^*\)-estimate
- Finite Disjunctive Programming Characterizations for General Mixed-Integer Linear Programs
- From the Mahler conjecture to Gauss linking integrals
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3484308 (Why is no real title available?)
- scientific article; zbMATH DE number 4119933 (Why is no real title available?)
- scientific article; zbMATH DE number 3046578 (Why is no real title available?)
- Inequalities from Two Rows of a Simplex Tableau
- Integer Programming with a Fixed Number of Variables
- Maximal lattice-free convex sets in linear subspaces
- Maximal lattice-free polyhedra: finiteness and an explicit description in dimension three
- New volume ratio properties for convex symmetric bodies in \({\mathbb{R}}^ n\)
- On t-branch split cuts for mixed-integer programs
- On convergence in mixed integer programming
- On mixed-integer sets with two integer variables
- On the rank of disjunctive cuts
- Outline of an algorithm for integer solutions to linear programs
- The Flatness Theorem for Nonsymmetric Convex Bodies via the Local Theory of Banach Spaces
- Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra
- Two row mixed-integer cuts via lifting
Cited in
(20)- On the relative strength of different generalizations of split cuts
- A local maximizer for lattice width of 3-dimensional hollow bodies
- Computing the covering radius of a polytope with an application to lonely runners
- Lattice-free simplices with lattice width \(2d - o(d)\)
- On the facet defining inequalities of the mixed-integer bilinear covering set
- Two row mixed-integer cuts via lifting
- Complexity of branch-and-bound and cutting planes in mixed-integer optimization
- On the rank of disjunctive cuts
- On the complexity of selecting disjunctions in integer programming
- An analysis of mixed integer linear sets based on lattice point free convex sets
- On an analysis of the strength of mixed-integer cutting planes from multiple simplex tableau rows
- On t-branch split cuts for mixed-integer programs
- Lower Bounds on the Lattice-Free Rank for Packing and Covering Integer Programs
- On the polyhedrality of closures of multibranch split sets and other polyhedra with bounded max-facet-width
- Hollow polytopes of large width
- Relaxations of mixed integer sets from lattice-free polyhedra
- Relaxations of mixed integer sets from lattice-free polyhedra
- Complexity of optimizing over the integers
- Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra
- 50 years of mixed-integer nonlinear and disjunctive programming
This page was built for publication: Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2248762)
