Outer approximation with conic certificates for mixed-integer convex problems

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...

Full description

Bibliographic Details
Main Authors: Coey, Chris, Lubin, Miles, Vielma, Juan P
Other Authors: Massachusetts Institute of Technology. Operations Research Center
Format: Article
Language:English
Published: Springer Berlin Heidelberg 2021
Online Access:https://hdl.handle.net/1721.1/131551
_version_ 1826208166128386048
author Coey, Chris
Lubin, Miles
Vielma, Juan P
author2 Massachusetts Institute of Technology. Operations Research Center
author_facet Massachusetts Institute of Technology. Operations Research Center
Coey, Chris
Lubin, Miles
Vielma, Juan P
author_sort Coey, Chris
collection MIT
description 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 $${{\mathcal {K}}}^*$$K∗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 $${{\mathcal {K}}}^*$$K∗ 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$${{\mathcal {K}}}^*$$K∗ cuts in order to tighten the polyhedral relaxations and thereby improve the speed of convergence, and propose fast heuristic methods of obtaining useful $${{\mathcal {K}}}^*$$K∗ cuts. Our new open source MI-conic solver Pajarito (github.com/JuliaOpt/Pajarito.jl) uses an external mixed-integer linear 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 $${{\mathcal {K}}}^*$$K∗ cuts.
first_indexed 2024-09-23T14:01:35Z
format Article
id mit-1721.1/131551
institution Massachusetts Institute of Technology
language English
last_indexed 2024-09-23T14:01:35Z
publishDate 2021
publisher Springer Berlin Heidelberg
record_format dspace
spelling mit-1721.1/1315512023-12-12T19:24:31Z Outer approximation with conic certificates for mixed-integer convex problems Coey, Chris Lubin, Miles Vielma, Juan P Massachusetts Institute of Technology. Operations Research Center Sloan School of Management 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 $${{\mathcal {K}}}^*$$K∗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 $${{\mathcal {K}}}^*$$K∗ 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$${{\mathcal {K}}}^*$$K∗ cuts in order to tighten the polyhedral relaxations and thereby improve the speed of convergence, and propose fast heuristic methods of obtaining useful $${{\mathcal {K}}}^*$$K∗ cuts. Our new open source MI-conic solver Pajarito (github.com/JuliaOpt/Pajarito.jl) uses an external mixed-integer linear 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 $${{\mathcal {K}}}^*$$K∗ cuts. 2021-09-20T17:20:21Z 2021-09-20T17:20:21Z 2020-02-20 2020-09-24T21:06:32Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/131551 en https://doi.org/10.1007/s12532-020-00178-3 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg
spellingShingle Coey, Chris
Lubin, Miles
Vielma, Juan P
Outer approximation with conic certificates for mixed-integer convex problems
title Outer approximation with conic certificates for mixed-integer convex problems
title_full Outer approximation with conic certificates for mixed-integer convex problems
title_fullStr Outer approximation with conic certificates for mixed-integer convex problems
title_full_unstemmed Outer approximation with conic certificates for mixed-integer convex problems
title_short Outer approximation with conic certificates for mixed-integer convex problems
title_sort outer approximation with conic certificates for mixed integer convex problems
url https://hdl.handle.net/1721.1/131551
work_keys_str_mv AT coeychris outerapproximationwithconiccertificatesformixedintegerconvexproblems
AT lubinmiles outerapproximationwithconiccertificatesformixedintegerconvexproblems
AT vielmajuanp outerapproximationwithconiccertificatesformixedintegerconvexproblems