Two row mixed-integer cuts via lifting
This article presents the characteristics of the lifting functions which provide the coefficients of the integer variables which define valid inequalities, or cuts, obtained from two rows of a general simplex tableau in a mixed-integer programming context. The paper begins with an overview of mixed-integer programs and cutting planes such as the facet-defining Gomory cuts. The authors expand this approach to derive strong cuts from two rows at a time. The second section contains the necessary background to mixed-integer group relaxations and lattice-free convex sets in two dimensions. This is followed by a description of the proposed approach to generate the cutting planes based on two rows of the tableau. This includes the various steps and an illustrative example of the proposed algorithm. The next four sections concentrate on the proof of the properties of the algorithm where a large number of relevant theorems are presented. This novel article concludes with a summary of the main findings, suggestions for future research and a list of relevant references.
- On mixing inequalities: rank, closure, and cutting-plane proofs
- Iterated Chvátal-Gomory cuts and the geometry of numbers
- Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming
- Pivot-and-reduce cuts: an approach for improving Gomory mixed-integer cuts
- Linear-programming-based lifting and its application to primal cutting-plane algorithms
- k-cuts: a variation of Gomory mixed integer cuts from the LP tableau
- A recursive procedure to generate all cuts for 0-1 mixed integer programs
- Characterization of facets for multiple right-hand choice linear programs
- Chvátal closures for mixed integer programming problems
- Corner polyhedra and their connection with cutting planes
- Cyclic group and knapsack facets
- Disjunctive Programming
- Elementary closures for integer programs.
- Facets of Two-Dimensional Infinite Group Problems
- scientific article; zbMATH DE number 193411 (Why is no real title available?)
- scientific article; zbMATH DE number 4119933 (Why is no real title available?)
- Inequalities from Two Rows of a Simplex Tableau
- Integer Programming and Pricing
- 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
- Mixed-integer cuts from cyclic groups
- New inequalities for finite and infinite group problems from approximate lifting
- On the Facets of Mixed Integer Programs with Two Integer Variables and Two Constraints
- On the strength of Gomory mixed-integer cuts as group cuts
- Sequential-Merge Facets for Two-Dimensional Group Problems
- Some continuous functions related to corner polyhedra
- Some continuous functions related to corner polyhedra, II
- Some polyhedra related to combinatorial problems
- Strengthening cuts for mixed integer programs
- T-space and cutting planes
- Two row mixed-integer cuts via lifting
- Valid inequalities based on simple mixed-integer sets
- Valid inequalities for mips and group polyhedra from approximate liftings
- Intersection cuts for single row corner relaxations
- Theoretical challenges towards cutting-plane selection
- Monoidal cut strengthening and generalized mixed-integer rounding for disjunctions and complementarity constraints
- Optimality certificates for convex minimization and Helly numbers
- Some cut-generating functions for second-order conic sets
- Two-row and two-column mixed-integer presolve using hashing-based pairing methods
- The triangle closure is a polyhedron
- Lattice-free sets, multi-branch split disjunctions, and mixed-integer programming
- Pivot-and-reduce cuts: an approach for improving Gomory mixed-integer cuts
- The (not so) trivial lifting in two dimensions
- An extremal property of lattice polygons
- A geometric approach to cut-generating functions
- A 3-slope theorem for the infinite relaxation in the plane
- The strength of multi-row models
- Two row mixed-integer cuts via lifting
- Cut-generating functions for integer variables
- Iterated Chvátal-Gomory cuts and the geometry of numbers
- Computational experiments with cross and crooked cross cuts
- On the practical strength of two-row tableau cuts
- Design and verify: A new scheme for generating cutting-planes
- When Lift-and-Project Cuts Are Different
- On the polyhedrality of cross and quadrilateral closures
- Operations that preserve the covering property of the lifting region
- Lifting Integer Variables in Minimal Inequalities Corresponding to Lattice-Free Triangles
- Experiments with two row tableau cuts
- Composite lifting of group inequalities and an application to two-row mixing inequalities
- A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts
- Monoidal cut strengthening revisited
- Intersection cuts from multiple rows: a disjunctive programming approach
- Can cut-generating functions be good and efficient?
- On the polyhedrality of closures of multibranch split sets and other polyhedra with bounded max-facet-width
- Approximate and exact merging of knapsack constraints with cover inequalities
- Nonunique lifting of integer variables in minimal inequalities
- Inequalities from Two Rows of a Simplex Tableau
- Relaxations of mixed integer sets from lattice-free polyhedra
- Lifting convex inequalities for bipartite bilinear programs
- Relaxations of mixed integer sets from lattice-free polyhedra
- Lifting convex inequalities for bipartite bilinear programs
- Monoidal strengthening and unique lifting in MIQCPs
- Monoidal strengthening of simple \(\mathcal{V} \)-polyhedral disjunctive cuts
- Towards a characterization of maximal quadratic-free sets
- Inequalities for the lattice width of lattice-free convex sets in the plane
- A characterization of maximal homogeneous-quadratic-free sets
- Monoidal strengthening of simple \(\mathcal{V} \)-polyhedral disjunctive cuts
- Monoidal strengthening and unique lifting in MIQCPs
- Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra
- Lifting properties of maximal lattice-free polyhedra
This page was built for publication: Two row mixed-integer cuts via lifting
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2638372)
