Outer approximation with conic certificates for mixed-integer convex problems
From MaRDI portal
Publication:2195682
DOI10.1007/S12532-020-00178-3zbMATH Open1441.90095arXiv1808.05290OpenAlexW3007427904MaRDI QIDQ2195682FDOQ2195682
Authors: Chris Coey, Miles Lubin, J. P. Vielma 
Publication date: 27 August 2020
Published in: Mathematical Programming Computation (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1808.05290
Recommendations
Convex programming (90C25) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Nonconvex programming, global optimization (90C26) Mixed integer programming (90C11)
Cites Work
- CSDP, A C library for semidefinite programming
- Disciplined convex programming
- SCIP: solving constraint integer programs
- CVXPY: a Python-embedded modeling language for convex optimization
- Julia: a fresh approach to numerical computing
- CBLIB 2014: a benchmark library for conic mixed-integer and continuous optimization
- JuMP: a modeling language for mathematical optimization
- Juniper: an open-source nonlinear branch-and-bound solver in Julia
- Extended formulations in mixed integer conic quadratic programming
- Title not available (Why is that?)
- Conic optimization via operator splitting and homogeneous self-dual embedding
- A note on performance profiles for benchmarking software
- Mixed-integer nonlinear optimization
- Benchmarking optimization software with performance profiles.
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- An algorithmic framework for convex mixed integer nonlinear programs
- Semidefinite programming relaxations for semialgebraic problems
- Algorithms and Software for Convex Mixed Integer Nonlinear Programs
- Perspective reformulation and applications
- On Polyhedral Approximations of the Second-Order Cone
- Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach
- Computing in operations research using Julia
- Extended formulations in mixed-integer convex programming
- Subgradient based outer approximation for mixed integer second order cone programming
- Second Order Cone Programming Relaxation of a Positive Semidefinite Constraint
- Polyhedral approximation in mixed-integer convex optimization
- Mixed-integer convex representability
- Experiments with conflict analysis in mixed integer programming
- A framework for solving mixed-integer semidefinite programs
- Sum of squares basis pursuit with linear and second order cone programming
- An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs
- Small and strong formulations for unions of convex sets from the Cayley embedding
Cited In (21)
- Polyhedral approximation in mixed-integer convex optimization
- Conflict Analysis for 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
- Fill‐rate service level constrained distribution network design
- Solving Natural Conic Formulations with Hypatia.jl
- Mixed-integer convex representability
- Extended formulations in mixed-integer convex programming
- Disjunctive cuts in mixed-integer conic optimization
- Cardinality-constrained distributionally robust portfolio optimization
- Mixed integer programming with a class of nonlinear convex constraints
- Subgradient based outer approximation for mixed integer second order cone programming
- Convex mixed integer nonlinear programming problems and an outer approximation algorithm
- Convex mixed-integer nonlinear programs derived from generalized disjunctive programming using cones
- Large-Scale Nonconvex Optimization: Randomization, Gap Estimation, and Numerical Resolution
- Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints
- Geometric and algebraic approaches to mixed-integer polynomial optimization using sos programming
- Bilevel cutting-plane algorithm for cardinality-constrained mean-CVaR portfolio optimization
- Alternative regularizations for outer-approximation algorithms for convex MINLP
- Generating feasible points for mixed-integer convex optimization problems by inner parallel cuts
- Improved regularity assumptions for partial outer convexification of mixed-integer PDE-constrained optimization problems
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)
