Outer approximation with conic certificates for mixed-integer convex problems
From MaRDI portal
Publication:2195682
Abstract: A mixed-integer convex (MI-convex) optimization problem is one that becomes convex when all integrality constraints are relaxed. We present a branch-and-bound LP outer approximation algorithm for an MI-convex problem transformed to MI-conic form. The polyhedral relaxations are refined with cuts derived from conic certificates for continuous primal-dual conic subproblems. Under the assumption that all subproblems are well-posed, the algorithm detects infeasibility or unboundedness or returns an optimal solution in finite time. Using properties of the conic certificates, we show that the cuts imply certain practically-relevant guarantees about the quality of the polyhedral relaxations, and demonstrate how to maintain helpful guarantees when the LP solver uses a positive feasibility tolerance. We discuss how to disaggregate cuts in order to tighten the polyhedral relaxations and thereby improve the speed of convergence, and propose fast heuristic methods of obtaining useful cuts. Our new open source MI-conic solver Pajarito (http://github.com/JuliaOpt/Pajarito.jl) uses an external mixed-integer linear (MILP) solver to manage the search tree and an external continuous conic solver for subproblems. Benchmarking on a library of mixed-integer second-order cone (MISOCP) problems, we find that Pajarito greatly outperforms Bonmin (the leading open source alternative) and is competitive with CPLEX's specialized MISOCP algorithm. We demonstrate the robustness of Pajarito by solving diverse MI-conic problems involving mixtures of positive semidefinite, second-order, and exponential cones, and provide evidence for the practical value of our analyses and enhancements of cuts.
Recommendations
Cites work
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- A framework for solving mixed-integer semidefinite programs
- A note on performance profiles for benchmarking software
- Algorithms and Software for Convex Mixed Integer Nonlinear Programs
- An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs
- An algorithmic framework for convex mixed integer nonlinear programs
- Benchmarking optimization software with performance profiles.
- CBLIB 2014: a benchmark library for conic mixed-integer and continuous optimization
- CSDP, A C library for semidefinite programming
- CVXPY: a Python-embedded modeling language for convex optimization
- Computing in operations research using Julia
- Conic optimization via operator splitting and homogeneous self-dual embedding
- Disciplined convex programming
- Experiments with conflict analysis in mixed integer programming
- Extended formulations in mixed integer conic quadratic programming
- Extended formulations in mixed-integer convex programming
- JuMP: a modeling language for mathematical optimization
- Julia: a fresh approach to numerical computing
- Juniper: an open-source nonlinear branch-and-bound solver in Julia
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Mixed-integer convex representability
- Mixed-integer nonlinear optimization
- On Polyhedral Approximations of the Second-Order Cone
- Perspective reformulation and applications
- Polyhedral approximation in mixed-integer convex optimization
- SCIP: solving constraint integer programs
- Second Order Cone Programming Relaxation of a Positive Semidefinite Constraint
- Semidefinite programming relaxations for semialgebraic problems
- Small and strong formulations for unions of convex sets from the Cayley embedding
- Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach
- Subgradient based outer approximation for mixed integer second order cone programming
- Sum of squares basis pursuit with linear and second order cone programming
Cited in
(21)- Extended formulations in mixed-integer convex programming
- Solving Natural Conic Formulations with Hypatia.jl
- Conflict Analysis for MINLP
- Subgradient based outer approximation for mixed integer second order cone programming
- Convex mixed-integer nonlinear programs derived from generalized disjunctive programming using cones
- Alternative regularizations for outer-approximation algorithms for convex MINLP
- A quadratically convergent sequential programming method for second-order cone programs capable of warm starts
- Conic programming models for production planning with clearing functions: formulations and duality
- Bilevel cutting-plane algorithm for cardinality-constrained mean-CVaR portfolio optimization
- Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints
- Fill‐rate service level constrained distribution network design
- Improved regularity assumptions for partial outer convexification of mixed-integer PDE-constrained optimization problems
- Mixed integer programming with a class of nonlinear convex constraints
- Convex mixed integer nonlinear programming problems and an outer approximation algorithm
- Large-Scale Nonconvex Optimization: Randomization, Gap Estimation, and Numerical Resolution
- Disjunctive cuts in mixed-integer conic optimization
- Geometric and algebraic approaches to mixed-integer polynomial optimization using sos programming
- Polyhedral approximation in mixed-integer convex optimization
- Cardinality-constrained distributionally robust portfolio optimization
- Generating feasible points for mixed-integer convex optimization problems by inner parallel cuts
- Mixed-integer convex representability
Describes a project that uses
Uses Software
This page was built for publication: Outer approximation with conic certificates for mixed-integer convex problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2195682)
