Intersection cuts for nonlinear integer programming: convexification techniques for structured sets

DOI10.1007/S10107-015-0866-5zbMATH Open1358.90078arXiv1302.2556OpenAlexW2029715007MaRDI QIDQ5962729FDOQ5962729

Mustafa R. Kılınç, J. P. Vielma, Sina Modaresi

Publication date: 23 February 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1302.2556

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

zbMATH Keywords

mixed integer nonlinear programmingsplitintersection cutsaggregation techniqueinterpolation technique\(k\)-branch splitconic quadratic sets

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Integer programming (90C10)

Cites Work

• SCIP: solving constraint integer programs
• A Survey of the S-Lemma
• Global optimization with polynomials and the problem of moments
• Title not available (Why is that?)
• Semidefinite programming relaxations for semialgebraic problems
• A branch-and-cut method for 0-1 mixed convex programming
• Some polyhedra related to combinatorial problems
• Outline of an algorithm for integer solutions to linear programs
• Mixed Integer Programming Computation
• Semidefinite Optimization and Convex Algebraic Geometry
• Title not available (Why is that?)
• Intersection Cuts—A New Type of Cutting Planes for Integer Programming
• Some continuous functions related to corner polyhedra
• Valid inequalities for mixed integer linear programs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications
• Progress in computational mixed integer programming -- a look back from the other side of the tipping point
• On the convex hull of a space curve
• The Convex Hull of a Variety
• A reformulation-linearization technique for solving discrete and continuous nonconvex problems
• Title not available (Why is that?)
• A Strong Dual for Conic Mixed-Integer Programs
• Handbook on semidefinite, conic and polynomial optimization
• Extending the QCR method to general mixed-integer programs
• Split closure and intersection cuts
• Split cuts and extended formulations for mixed integer conic quadratic programming
• A recursive procedure to generate all cuts for 0-1 mixed integer programs
• The split closure of a strictly convex body
• On families of quadratic surfaces having fixed intersections with two hyperplanes
• Edmonds polytopes and a hierarchy of combinatorial problems
• Cutting-Planes for Optimization of Convex Functions over Nonconvex Sets
• A Conic Representation of the Convex Hull of Disjunctive Sets and Conic Cuts for Integer Second Order Cone Optimization
• Title not available (Why is that?)
• Intersection Cuts for Mixed Integer Conic Quadratic Sets
• Conic mixed-integer rounding cuts
• Chvátal closures for mixed integer programming problems
• Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition
• Semidefinite programming relaxation for nonconvex quadratic programs
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• Cuts for mixed 0-1 conic programming
• Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets
• Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
• Generalized intersection cuts and a new cut generating paradigm
• A constructive characterization of the split closure of a mixed integer linear program
• An Analysis of Mixed Integer Linear Sets Based on Lattice Point Free Convex Sets
• Title not available (Why is that?)
• Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra
• Cook, Kannan and Schrijver's example revisited
• Equivalence between intersection cuts and the corner polyhedron
• SDP relaxations in combinatorial optimization from a Lagrangian viewpoint.
• A New Approach to the Stable Set Problem Based on Ellipsoids
• Polyhedral Approaches to Mixed Integer Linear Programming
• An effective branch-and-bound algorithm for convex quadratic integer programming
• ORBITOPES
• An Effective Branch-and-Bound Algorithm for Convex Quadratic Integer Programming
• Relaxations of mixed integer sets from lattice-free polyhedra
• Semidefinite Representation of Convex Sets and Convex Hulls
• Convex Hulls of Algebraic Sets
• Lift-and-project cuts for convex mixed integer nonlinear programs
• Lift-and-Project Cuts for Mixed Integer Convex Programs
• Convex hull of two quadratic constraints is an LMI set
• Aggregation and Mixed Integer Rounding to Solve MIPs
• Integer programming and combinatoral optimization. 15th international conference, IPCO 2011, New York, NY, USA, June 15--17, 2011. Proceedings
• Cuts for Conic Mixed-Integer Programming
• A note on the MIR closure and basic relaxations of polyhedra
• Semidefinite representation of convex hulls of rational varieties
• Convex hulls of curves of genus one
• Computational Experiments with Cross and Crooked Cross Cuts
• Integer programming and combinatorial optimization. 14th international conference, IPCO 2010, Lausanne, Switzerland, June 9--11, 2010. Proceedings
• The Chvátal-Gomory closure of a strictly convex body
• On the Chvátal-Gomory Closure of a Compact Convex Set
• The Chvátal-Gomory Closure of an Ellipsoid Is a Polyhedron
• Title not available (Why is that?)

Cited In (26)

• On a generalization of the Chvátal-Gomory closure
• Submodularity in Conic Quadratic Mixed 0–1 Optimization
• On the facet defining inequalities of the mixed-integer bilinear covering set
• Convexification of Queueing Formulas by Mixed-Integer Second-Order Cone Programming: An Application to a Discrete Location Problem with Congestion
• Maximal quadratic-free sets
• Lift-and-project cuts for convex mixed integer nonlinear programs
• 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
• On the Convexification of Constrained Quadratic Optimization Problems with Indicator Variables
• Convex hull of two quadratic or a conic quadratic and a quadratic inequality
• 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
• Disjunctive cuts in mixed-integer conic optimization
• Two-term disjunctions on the second-order cone
• On the implementation and strengthening of intersection cuts for QCQPs
• On the use of intersection cuts for bilevel optimization
• Intersection cuts from multiple rows: a disjunctive programming approach
• Maximal Quadratic-Free Sets
• Split cuts and extended formulations for mixed integer conic quadratic programming
• Ideal formulations for constrained convex optimization problems with indicator variables
• Strong formulations for quadratic optimization with M-matrices and indicator variables
• On the implementation and strengthening of intersection cuts for QCQPs
• Towards a characterization of maximal quadratic-free sets

Uses Software

• SCIP

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)