Intersection cuts for nonlinear integer programming: convexification techniques for structured sets
From MaRDI portal
Publication:5962729
Abstract: We study the generalization of split, k-branch split, and intersection cuts from Mixed Integer Linear Programming to the realm of Mixed Integer Nonlinear Programming. Constructing such cuts requires calculating the convex hull of the difference between a convex set and an open set with a simple geometric structure. We introduce two techniques to give precise characterizations of such convex hulls and use them to construct split, k-branch split, and intersection cuts for several classes of non-polyhedral sets. In particular, we give simple formulas for split cuts for essentially all convex sets described by a single quadratic inequality. We also give simple formulas for k-branch split cuts and some general intersection cuts for a wide variety of convex quadratic sets.
Recommendations
- Intersection cuts for mixed integer conic quadratic sets
- Lift-and-project cuts for mixed integer convex programs
- Cuts for Conic Mixed-Integer Programming
- Strong valid inequalities for orthogonal disjunctions and bilinear covering sets
- Split cuts and extended formulations for mixed integer conic quadratic programming
Cites work
- scientific article; zbMATH DE number 47153 (Why is no real title available?)
- scientific article; zbMATH DE number 193411 (Why is no real title available?)
- scientific article; zbMATH DE number 1312984 (Why is no real title available?)
- scientific article; zbMATH DE number 4119933 (Why is no real title available?)
- scientific article; zbMATH DE number 2120513 (Why is no real title available?)
- scientific article; zbMATH DE number 2196290 (Why is no real title available?)
- A Survey of the S-Lemma
- A branch-and-cut method for 0-1 mixed convex programming
- A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization
- A constructive characterization of the split closure of a mixed integer linear program
- A new approach to the stable set problem based on ellipsoids
- A note on the MIR closure and basic relaxations of polyhedra
- A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
- A recursive procedure to generate all cuts for 0-1 mixed integer programs
- A reformulation-linearization technique for solving discrete and continuous nonconvex problems
- A strong dual for conic mixed-integer programs
- Aggregation and Mixed Integer Rounding to Solve MIPs
- An analysis of mixed integer linear sets based on lattice point free convex sets
- An effective branch-and-bound algorithm for convex quadratic integer programming
- An effective branch-and-bound algorithm for convex quadratic integer programming
- Chvátal closures for mixed integer programming problems
- Computational experiments with cross and crooked cross cuts
- Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets
- Conic mixed-integer rounding cuts
- Convex hull of two quadratic constraints is an LMI set
- Convex hulls of algebraic sets
- Convex hulls of curves of genus one
- Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications
- Cook, Kannan and Schrijver's example revisited
- Cuts for Conic Mixed-Integer Programming
- Cuts for mixed 0-1 conic programming
- Cutting-Planes for Optimization of Convex Functions over Nonconvex Sets
- Edmonds polytopes and a hierarchy of combinatorial problems
- Equivalence between intersection cuts and the corner polyhedron
- Extending the QCR method to general mixed-integer programs
- Generalized intersection cuts and a new cut generating paradigm
- Global optimization with polynomials and the problem of moments
- Handbook on semidefinite, conic and polynomial optimization
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- Integer programming and combinatoral optimization. 15th international conference, IPCO 2011, New York, NY, USA, June 15--17, 2011. Proceedings
- Integer programming and combinatorial optimization. 14th international conference, IPCO 2010, Lausanne, Switzerland, June 9--11, 2010. Proceedings
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- Intersection cuts for mixed integer conic quadratic sets
- LMI representations of the convex hulls of quadratic basic semialgebraic sets
- Lift-and-project cuts for convex mixed integer nonlinear programs
- Lift-and-project cuts for mixed integer convex programs
- Mixed integer programming computation
- Mixed integer second order cone programming.
- ORBITOPES
- On families of quadratic surfaces having fixed intersections with two hyperplanes
- On the Chvátal-Gomory closure of a compact convex set
- On the convex hull of a space curve
- Outline of an algorithm for integer solutions to linear programs
- Polyhedral approaches to mixed integer linear programming
- Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition
- Progress in computational mixed integer programming -- a look back from the other side of the tipping point
- Relaxations of mixed integer sets from lattice-free polyhedra
- SCIP: solving constraint integer programs
- SDP relaxations in combinatorial optimization from a Lagrangian viewpoint.
- Semidefinite Optimization and Convex Algebraic Geometry
- Semidefinite Representation of Convex Sets and Convex Hulls
- Semidefinite programming relaxation for nonconvex quadratic programs
- Semidefinite programming relaxations for semialgebraic problems
- Semidefinite representation of convex hulls of rational varieties
- Some continuous functions related to corner polyhedra
- Some polyhedra related to combinatorial problems
- Split closure and intersection cuts
- Split cuts and extended formulations for mixed integer conic quadratic programming
- The Chvátal-Gomory Closure of an Ellipsoid Is a Polyhedron
- The Chvátal-Gomory closure of a strictly convex body
- The convex hull of a variety
- The split closure of a strictly convex body
- Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra
- Valid inequalities for mixed integer linear programs
Cited in
(33)- On a generalization of the Chvátal-Gomory closure
- On the facet defining inequalities of the mixed-integer bilinear covering set
- Submodularity in Conic Quadratic Mixed 0–1 Optimization
- Lift-and-project cuts for convex mixed integer nonlinear programs
- Maximal quadratic-free sets
- Maximal quadratic-free sets
- Intersection cuts for polynomial optimization
- Outer-product-free sets for polynomial optimization and oracle-based cuts
- A complete characterization of disjunctive conic cuts for mixed integer second order cone optimization
- Intersection cuts for convex mixed integer programs from translated cones
- Convex hull of two quadratic or a conic quadratic and a quadratic inequality
- Strong valid inequalities for orthogonal disjunctions and bilinear covering sets
- Scanning integer points with lex-inequalities: a finite cutting plane algorithm for integer programming with linear objective
- On sublinear inequalities for mixed integer conic programs
- Strong formulations for conic quadratic optimization with indicator variables
- How to convexify the intersection of a second order cone and a nonconvex quadratic
- Convexification of queueing formulas by mixed-integer second-order cone programming: an application to a discrete location problem with congestion
- On interval-subgradient and no-good cuts
- Two-term disjunctions on the second-order cone
- Intersection cuts for factorable MINLP
- Disjunctive cuts in mixed-integer conic optimization
- On the implementation and strengthening of intersection cuts for QCQPs
- Intersection cuts from multiple rows: a disjunctive programming approach
- On the use of intersection cuts for bilevel optimization
- On the convexification of constrained quadratic optimization problems with indicator variables
- Split cuts and extended formulations for mixed integer conic quadratic programming
- Ideal formulations for constrained convex optimization problems with indicator variables
- Intersection cuts for mixed integer conic quadratic sets
- Strong formulations for quadratic optimization with M-matrices and indicator variables
- On the implementation and strengthening of intersection cuts for QCQPs
- On pathological disjunctions and redundant disjunctive conic cuts
- Towards a characterization of maximal quadratic-free sets
- Depth-optimized convexity cuts
This page was built for publication: Intersection cuts for nonlinear integer programming: convexification techniques for structured sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5962729)
