Polyhedral approximation in mixed-integer convex optimization

Miles Lubin, Emre Yamangil, Russell Bent, Juan Pablo VielmaMath. Program 2018 · DOI

TL;DR

This paper introduces a novel approach to solving mixed-integer convex optimization (MICP) problems by leveraging "disciplined convex programming" (DCP) to automatically generate stronger polyhedral outer approximations. This method significantly improves the performance of existing solvers and allows for the solution of previously intractable problems.

What Problem Does This Paper Address?

Mixed-integer convex optimization (MICP) is a powerful framework for modeling complex real-world problems, but it has lagged behind mixed-integer linear programming (MILP) in terms of solver capabilities. A key challenge in solving MICP is efficiently handling the non-linear convex constraints. Traditional methods like outer approximation (OA) rely on approximating these convex sets with polyhedra (linear inequalities). However, these approximations can be weak, leading to a large number of iterations and slow convergence, especially for problems with certain types of convex constraints. This paper aims to bridge this gap by developing a more robust and automated way to create these polyhedral approximations.

Methods

The core of the paper's contribution lies in its use of Disciplined Convex Programming (DCP). DCP is a modeling paradigm that ensures convexity by enforcing specific composition rules. The authors argue that this structured approach to defining convex constraints naturally lends itself to generating extended formulations. Extended formulations introduce auxiliary variables to create a more compact and stronger polyhedral representation of the original convex constraints.

The authors propose using DCP to automatically translate MICP problems into a mixed-integer conic optimization (MICONE) form. This conic representation is then used as input for an outer approximation algorithm. The key innovation is that the DCP structure allows for the automated generation of these stronger polyhedral approximations, effectively overcoming the limitations of traditional OA methods that rely on manual formulation or less structured convex constraint representations. They also extend the standard OA algorithm to handle conic problems, which are more general than smooth convex problems.

Datasets

The authors evaluated their approach on instances from the MINLPLIB2 benchmark library. They translated 194 convex instances into DCP form. They also mention classifying all 333 MICP instances from MINLPLIB2 to understand their conic representability.

Key Insights and Ideas

  • DCP as a bridge to extended formulations: The structured nature of DCP, where convexity is proven through composition rules, provides a natural way to automatically generate extended formulations. This is a significant step towards automating a technique that was previously manual and complex.
  • Conic representation is powerful and compact: The paper highlights that representing MICP problems in a mixed-integer conic form is a compact and efficient way to encode the necessary information for extended formulations. This conic view is argued to be more general and superior to the traditional "black-box" approach for many problems.
  • Extended formulations significantly reduce OA iterations: By constructing stronger polyhedral approximations, the authors demonstrate that their approach drastically reduces the number of iterations required by the outer approximation algorithm.
  • The challenge of non-differentiable and non-self-dual cones: The paper acknowledges that while conic form handles non-differentiability well, the convergence theory of OA algorithms can be challenged when strong duality doesn't hold in continuous conic subproblems. They provide a theoretical example where polyhedral approximations fail entirely.

Key Results

  • Improved performance: The authors' solver, Pajarito, built on these ideas, shows superior performance compared to state-of-the-art solvers like Bonmin, SCIP, and Artelys Knitro on the MINLPLIB2 benchmark instances.
  • Fewer iterations: Pajarito required significantly fewer outer approximation iterations (994) compared to Bonmin (2685) on average across tested instances.
  • Solution of previously unsolved instances: Pajarito was able to solve a previously unsolved instance, gams01, which required a mix of SOC and EXP cones. This instance was solved to optimality with an objective value of 21380.20 in just 6 iterations.
  • Comparison with CPLEX: For MISOCP instances, Pajarito was competitive with CPLEX, which is noted to already implement extended formulations.

Limitations and Future Work

  • Reliability of conic solvers: The authors mention that while their approach has advanced, the capabilities of existing conic solvers, especially for non-symmetric cones, still need improvement.
  • Strong duality assumptions: The theoretical analysis highlights cases where strong duality might fail in continuous conic subproblems, potentially leading to infinite convergence for the OA algorithm. The paper suggests further investigation into how to handle these situations, possibly by automatically detecting and resolving them at the DCP level.
  • Branch-and-cut variant: The authors plan to explore a branch-and-cut variant of their algorithm.
  • Mixed-integer semidefinite optimization: They intend to investigate the application of polyhedral approximation in the context of mixed-integer semidefinite optimization, where duality failures might be more common.
  • Uniqueness of formulations: The paper notes that DCP and conic representations are not always unique, and understanding the impact of different formulation choices is an important area for future research.

Summary updated

BibTeX
@article{lubin2018polyhedral,
  author = {Miles Lubin and Emre Yamangil and Russell Bent and Juan Pablo Vielma},
  title = {{Polyhedral approximation in mixed-integer convex optimization}},
  journal = {Math. Program.},
  year = {2018},
  doi = {10.1007/s10107-017-1191-y},
}

Loading related content...

Figure