On minimal valid inequalities for mixed integer conic programs
From MaRDI portal
Publication:2806815
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.
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
Cites work
- A branch-and-cut method for 0-1 mixed convex programming
- A complementarity-based partitioning and disjunctive cut algorithm for mathematical programming problems with equilibrium constraints
- A conic integer programming approach to stochastic joint location-inventory problems
- A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization
- A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs
- A strong dual for conic mixed-integer programs
- An LMI description for the cone of Lorentz-positive maps
- An LMI description for the cone of Lorentz-positive maps. II
- An algorithmic framework for convex mixed integer nonlinear programs
- An effective branch-and-bound algorithm for convex quadratic integer programming
- Cardinality Constrained Linear-Quadratic Optimal Control
- Clustering via minimum volume ellipsoids
- Conic mixed-integer rounding cuts
- Convex sets and minimal sublinear functions
- Convexification and global optimization in continuous and mixed-integer nonlinear programming. Theory, algorithms, software, and applications
- Convexification techniques for linear complementarity constraints
- Cut-generating functions and \(S\)-free sets
- Cut-generating functions for integer variables
- Cuts for mixed 0-1 conic programming
- Cutting-Planes for Optimization of Convex Functions over Nonconvex Sets
- Cutting-planes for weakly-coupled \(0/1\) second order cone programs
- Disjunctive Cuts for Non-convex Mixed Integer Quadratically Constrained Programs
- Disjunctive Programming
- Disjunctive cuts for cross-sections of the second-order cone
- Equivalence between intersection cuts and the corner polyhedron
- Global optimization of mixed-integer nonlinear programs: a theoretical and computational study
- How to convexify the intersection of a second order cone and a nonconvex quadratic
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- Inequalities from Two Rows of a Simplex Tableau
- Integer programming and combinatoral optimization. 15th international conference, IPCO 2011, New York, NY, USA, June 15--17, 2011. Proceedings
- Integer programming and convex analysis: Intersection cuts from outer polars
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- Intersection cuts for mixed integer conic quadratic sets
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Lift-and-project cuts for mixed integer convex programs
- Lifting for conic mixed-integer programming
- Linear programming relaxations of quadratically constrained quadratic programs
- Minimal inequalities
- Minimal valid inequalities for integer constraints
- Mixed integer second order cone programming.
- Mixed-integer nonlinear optimization
- On the facets of mixed integer programs with two integer variables and two constraints
- Portfolio optimization with linear and fixed transaction costs
- Robust convex optimization
- Semidefinite programming in combinatorial optimization
- Solving Nonlinear Single-Unit Commitment Problems with Ramping Constraints
- Some continuous functions related to corner polyhedra
- Some continuous functions related to corner polyhedra, II
- Some polyhedra related to combinatorial problems
- Sparse learning via Boolean relaxations
- Sufficiency of cut-generating functions
- The MILP road to MIQCP
- The split closure of a strictly convex body
- Two-term disjunctions on the second-order cone
- Valid inequalities for mixed integer linear programs
Cited in
(24)- On the implementation and strengthening of intersection cuts for QCQPs
- On SOCP-based disjunctive cuts for solving a class of integer bilevel nonlinear programs
- Maximal quadratic-free sets
- Quadratic cone cutting surfaces for quadratic programs with on-off constraints
- Strong formulations for conic quadratic optimization with indicator variables
- How to convexify the intersection of a second order cone and a nonconvex quadratic
- Maximal quadratic-free sets
- 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
- Outer-product-free sets for polynomial optimization and oracle-based cuts
- Submodularity in Conic Quadratic Mixed 0–1 Optimization
- Mixed integer programming with a class of nonlinear convex constraints
- On sublinear inequalities for mixed integer conic programs
- Disjunctive cuts in mixed-integer conic optimization
- Convex hull of two quadratic or a conic quadratic and a quadratic inequality
- 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
- Two-term disjunctions on the second-order cone
- Intersection cuts for convex mixed integer programs from translated cones
- Some cut-generating functions for second-order conic sets
- Convexification of queueing formulas by mixed-integer second-order cone programming: an application to a discrete location problem with congestion
- Minimal valid inequalities for integer constraints
- On the implementation and strengthening of intersection cuts for QCQPs
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)
