Optimization Online


Outer Approximation With Conic Certificates For Mixed-Integer Convex Problems

Chris Coey(coey***at***mit.edu)
Miles Lubin(miles.lubin***at***gmail.com)
Juan Pablo Vielma(jvielma***at***mit.edu)

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 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 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 K* cuts in order to tighten the polyhedral relaxations and thereby improve the speed of convergence, and propose fast heuristic methods of obtaining useful K* cuts. Our new open source MI-conic solver Pajarito 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 K* cuts.

Keywords: Convex MINLP, Outer Approximation, Conic Duality

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Optimization Software and Modeling Systems (Optimization Software Benchmark )

Category 3: Linear, Cone and Semidefinite Programming


Download: [PDF]

Entry Submitted: 08/17/2018
Entry Accepted: 08/17/2018
Entry Last Modified: 08/17/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society