Extended formulations in mixed-integer convex programming
From MaRDI portal
Abstract: We present a unifying framework for generating extended formulations for the polyhedral outer approximations used in algorithms for mixed-integer convex programming (MICP). Extended formulations lead to fewer iterations of outer approximation algorithms and generally faster solution times. First, we observe that all MICP instances from the MINLPLIB2 benchmark library are conic representable with standard symmetric and nonsymmetric cones. Conic reformulations are shown to be effective extended formulations themselves because they encode separability structure. For mixed-integer conic-representable problems, we provide the first outer approximation algorithm with finite-time convergence guarantees, opening a path for the use of conic solvers for continuous relaxations. We then connect the popular modeling framework of disciplined convex programming (DCP) to the existence of extended formulations independent of conic representability. We present evidence that our approach can yield significant gains in practice, with the solution of a number of open instances from the MINLPLIB2 benchmark library.
Recommendations
- Polyhedral approximation in mixed-integer convex optimization
- Extended formulations in mixed integer conic quadratic programming
- Outer approximation with conic certificates for mixed-integer convex problems
- An Outer-Inner Approximation for Separable Mixed-Integer Nonlinear Programs
- Split cuts and extended formulations for mixed integer conic quadratic programming
Cites work
- A polyhedral branch-and-cut approach to global optimization
- Algorithms and Software for Convex Mixed Integer Nonlinear Programs
- An active-set method for second-order conic-constrained quadratic programming
- An algorithmic framework for convex mixed integer nonlinear programs
- An Outer-Inner Approximation for Separable Mixed-Integer Nonlinear Programs
- Applications of second-order cone programming
- Branch and Bound Experiments in Convex Nonlinear Integer Programming
- Computing in operations research using Julia
- Different transformations for solving non-convex trim-loss problems by MINLP
- Differential properties of Euclidean projection onto power cone
- Disciplined convex programming
- Extended formulations in mixed integer conic quadratic programming
- Extended formulations in mixed-integer convex programming
- FilMINT: an outer approximation-based solver for convex mixed-integer nonlinear programs
- scientific article; zbMATH DE number 5066287 (Why is no real title available?)
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Mixed-integer nonlinear optimization
- NP-hardness of deciding convexity of quartic polynomials and related problems
- Perspective reformulation and applications
- SCIP: solving constraint integer programs
- Solving mixed integer nonlinear programs by outer approximation
- Subgradient based outer approximation for mixed integer second order cone programming
Cited in
(24)- Extended formulations in mixed integer conic quadratic programming
- Polyhedral approximation in mixed-integer convex optimization
- A finite \(\epsilon\)-convergence algorithm for two-stage stochastic convex nonlinear programs with mixed-binary first and second-stage variables
- Sparse regression at scale: branch-and-bound rooted in first-order optimization
- A primal-dual interior-point algorithm for nonsymmetric exponential-cone optimization
- The supporting hyperplane optimization toolkit for convex MINLP
- Outer approximation with conic certificates for mixed-integer convex problems
- Least costly energy management for extended-range electric vehicles: an economic optimization framework
- Mixed-integer bilevel representability
- Algorithms for joint sensor and control nodes selection in dynamic networks
- Small and strong formulations for unions of convex sets from the Cayley embedding
- Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations
- Extended formulations in mixed-integer convex programming
- An algorithm for nonsymmetric conic optimization inspired by MOSEK
- Solving Natural Conic Formulations with Hypatia.jl
- Mixed-integer convex representability
- Strategic workforce planning under uncertainty
- Disjunctive cuts in mixed-integer conic optimization
- Projection onto the exponential cone: a univariate root-finding problem
- Convex mixed-integer nonlinear programs derived from generalized disjunctive programming using cones
- Binary extended formulations and sequential convexification
- Instance-specific linear relaxations of semidefinite optimization problems
- Reformulations for utilizing separability when solving convex MINLP problems
- Symmetry detection in mixed-integer conic programming
This page was built for publication: Extended formulations in mixed-integer convex programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3186495)
