On minimal valid inequalities for mixed integer conic programs
From MaRDI portal
Publication:2806815
DOI10.1287/MOOR.2015.0737zbMATH Open1338.90275arXiv1408.6922OpenAlexW1877367452MaRDI QIDQ2806815FDOQ2806815
Authors: Fatma Kılınç-Karzan 
Publication date: 19 May 2016
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Abstract: We study disjunctive conic sets involving a general regular (closed, convex, full dimensional, and pointed) cone K such as the nonnegative orthant, the Lorentz cone or the positive semidefinite cone. In a unified framework, we introduce K-minimal inequalities and show that under mild assumptions, these inequalities together with the trivial cone-implied inequalities are sufficient to describe the convex hull. We study the properties of K-minimal inequalities by establishing algebraic necessary conditions for an inequality to be K-minimal. This characterization leads to a broader algebraically defined class of K- sublinear inequalities. We establish a close connection between K-sublinear inequalities and the support functions of sets with a particular structure. This connection results in practical ways of showing that a given inequality is K-sublinear and K-minimal. Our framework generalizes some of the results from the mixed integer linear case. It is well known that the minimal inequalities for mixed integer linear programs are generated by sublinear (positively homogeneous, subadditive and convex) functions that are also piecewise linear. This result is easily recovered by our analysis. Whenever possible we highlight the connections to the existing literature. However, our study unveils that such a cut generating function view treating the data associated with each individual variable independently is not possible in the case of general cones other than nonnegative orthant, even when the cone involved is the Lorentz cone.
Full work available at URL: https://arxiv.org/abs/1408.6922
Recommendations
- On valid inequalities for mixed integer \(p\)-order cone programming
- Valid inequalities for mixed integer linear programs
- On sublinear inequalities for mixed integer conic programs
- Minimal infeasible constraint sets in convex integer programs
- scientific article; zbMATH DE number 3920195
- Integer convex minimization by mixed integer linear optimization
- A general purpose exact solution method for mixed integer concave minimization problems
- Valid inequalities for mixed-integer programmes with fixed charges on sets of variables
- A note on the minimal cone for conic linear programming
- Minimal valid inequalities for integer constraints
Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Mixed integer programming (90C11)
Cites Work
- Mixed-integer nonlinear optimization
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- An algorithmic framework for convex mixed integer nonlinear programs
- A branch-and-cut method for 0-1 mixed convex programming
- Portfolio optimization with linear and fixed transaction costs
- Some polyhedra related to combinatorial problems
- A conic integer programming approach to stochastic joint location-inventory problems
- Minimal valid inequalities for integer constraints
- Cut-generating functions and \(S\)-free sets
- Inequalities from Two Rows of a Simplex Tableau
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- Some continuous functions related to corner polyhedra
- Some continuous functions related to corner polyhedra, II
- Valid inequalities for mixed integer linear programs
- Robust convex optimization
- Solving Nonlinear Single-Unit Commitment Problems with Ramping Constraints
- Disjunctive Programming
- Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications
- Global optimization of mixed-integer nonlinear programs: a theoretical and computational study
- A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs
- Mixed integer second order cone programming.
- Minimal inequalities
- A strong dual for conic mixed-integer programs
- Disjunctive cuts for cross-sections of the second-order cone
- The split closure of a strictly convex body
- 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
- Intersection cuts for mixed integer conic quadratic sets
- Sufficiency of cut-generating functions
- How to convexify the intersection of a second order cone and a nonconvex quadratic
- Two-term disjunctions on the second-order cone
- Conic mixed-integer rounding cuts
- On the facets of mixed integer programs with two integer variables and two constraints
- The MILP road to MIQCP
- Linear programming relaxations of quadratically constrained quadratic programs
- Cuts for mixed 0-1 conic programming
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- Integer programming and convex analysis: Intersection cuts from outer polars
- Equivalence between intersection cuts and the corner polyhedron
- An LMI description for the cone of Lorentz-positive maps. II
- An LMI description for the cone of Lorentz-positive maps
- An effective branch-and-bound algorithm for convex quadratic integer programming
- Cardinality Constrained Linear-Quadratic Optimal Control
- Semidefinite programming in combinatorial optimization
- Convexification techniques for linear complementarity constraints
- Convex sets and minimal sublinear functions
- A complementarity-based partitioning and disjunctive cut algorithm for mathematical programming problems with equilibrium constraints
- Cutting-planes for weakly-coupled \(0/1\) second order cone programs
- Lift-and-project cuts for mixed integer convex programs
- Disjunctive Cuts for Non-convex Mixed Integer Quadratically Constrained Programs
- Integer programming and combinatoral optimization. 15th international conference, IPCO 2011, New York, NY, USA, June 15--17, 2011. Proceedings
- Lifting for conic mixed-integer programming
- Clustering via minimum volume ellipsoids
- Cut-generating functions for integer variables
- Sparse learning via Boolean relaxations
Cited In (25)
- Submodularity in Conic Quadratic Mixed 0–1 Optimization
- Maximal quadratic-free sets
- Maximal quadratic-free sets
- On SOCP-based disjunctive cuts for solving a class of integer bilevel nonlinear programs
- Outer-product-free sets for polynomial optimization and oracle-based cuts
- Intersection cuts for convex mixed integer programs from translated cones
- Some cut-generating functions for second-order conic sets
- Convex hull of two quadratic or a conic quadratic and a quadratic inequality
- Minimal valid inequalities for integer constraints
- On sublinear inequalities for mixed integer conic programs
- Strong formulations for conic quadratic optimization with indicator variables
- Quadratic cone cutting surfaces for quadratic programs with on-off constraints
- 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
- 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
- Mixed integer programming with a class of nonlinear convex constraints
- Scenario-based cuts for structured two-stage stochastic and distributionally robust \(p\)-order conic mixed integer programs
- A combinatorial cut-and-lift procedure with an application to 0-1 second-order conic programming
- Convex mixed-integer nonlinear programs derived from generalized disjunctive programming using cones
- Cut-generating functions for integer variables
- Split cuts and extended formulations for mixed integer conic quadratic programming
- The structure of the infinite models in integer programming
- On the implementation and strengthening of intersection cuts for QCQPs
Uses Software
This page was built for publication: On minimal valid inequalities for mixed integer conic programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2806815)
