Intersection cuts from multiple rows: a disjunctive programming approach
From MaRDI portal
Publication:458123
DOI10.1007/S13675-013-0008-XzbMATH Open1296.90080arXiv1206.1630OpenAlexW2037710606MaRDI QIDQ458123FDOQ458123
Authors: E. Balas, A. Qualizza 
Publication date: 30 September 2014
Published in: EURO Journal on Computational Optimization (Search for Journal in Brave)
Abstract: We address the issue of generating cutting planes for mixed integer programs from multiple rows of the simplex tableau with the tools of disjunctive programming. A cut from q rows of the simplex tableau is an intersection cuts from a q-dimensional parametric cross-polytope, which can also be viewed as a disjunctive cut from a 2q-term disjunction. We define the disjunctive hull of the q-row problem, describe its relation to the integer hull, and show how to generate its facets. For the case of binary basic variables, we derive cuts from the stronger disjunctions whose terms are equations. We give cut strengthening procedures using the integrality of the nonbasic variables for both the integer and the binary case. Finally, we discuss some computational experiments.
Full work available at URL: https://arxiv.org/abs/1206.1630
Recommendations
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- Multirow Intersection Cuts Based on the Infinity Norm
- On disjunctive cuts for combinatorial optimization
- Intersection cuts for single row corner relaxations
- Disjunctive cuts for mixed integer nonlinear programming problems
- Disjunctive cuts in mixed-integer conic optimization
- A disjunctive cutting plane procedure for general mixed-integer linear programs
- Intersection cuts for nonlinear integer programming: convexification techniques for structured sets
- Generalized intersection cuts and a new cut generating paradigm
- An algorithm for the separation of two-row cuts
Cites Work
- Strengthening cuts for mixed integer programs
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- Some polyhedra related to combinatorial problems
- Two row mixed-integer cuts via lifting
- Minimal valid inequalities for integer constraints
- Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework
- Inequalities from Two Rows of a Simplex Tableau
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- Disjunctive programming: Properties of the convex hull of feasible points
- Disjunctive Programming
- On the relative strength of split, triangle and quadrilateral cuts
- Chvátal closures for mixed integer programming problems
- On the facets of mixed integer programs with two integer variables and two constraints
- A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming
- Equivalence between intersection cuts and the corner polyhedron
- Testing cut generators for mixed-integer linear programming
- Experiments with two-row cuts from degenerate tableaux
- Experiments with two row tableau cuts
Cited In (12)
- Experiments with two-row cuts from degenerate tableaux
- On the separation of disjunctive cuts
- Computing with multi-row gomory cuts
- Monoidal cut strengthening revisited
- Facet inequalities from simple disjunctions in cutting plane theory
- Multirow Intersection Cuts Based on the Infinity Norm
- Sparse multi-term disjunctive cuts for the epigraph of a function of binary variables
- Monoidal strengthening of simple \(\mathcal{V} \)-polyhedral disjunctive cuts
- On the relationship between standard intersection cuts, lift-and-project cuts, and generalized intersection cuts
- When Lift-and-Project Cuts Are Different
- Intersection cuts for single row corner relaxations
- Generalized intersection cuts and a new cut generating paradigm
Uses Software
This page was built for publication: Intersection cuts from multiple rows: a disjunctive programming approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q458123)
