Extended Formulations in Mixed-Integer Convex Programming

Miles Lubin, Emre Yamangil, Russell Bent, Juan Pablo VielmaIPCO 2016 · DOI

TL;DR

This paper introduces a unifying framework for generating "extended formulations" for mixed-integer convex programming (MICP) problems. By reformulating these problems into a conic form, the authors demonstrate significant improvements in solver performance and enable the solution of previously intractable instances.

What Problem Does This Paper Address?

Mixed-integer convex programming (MICP) is a powerful tool for solving optimization problems with both continuous and integer variables, subject to convex constraints. However, solving these problems can be computationally challenging. Traditional approaches often rely on polyhedral outer approximations, which can be weak and lead to many iterations. While "extended formulations" (adding auxiliary variables to create stronger polyhedral approximations) have shown promise, especially for separable problems and second-order cone programs, a general and unifying framework for MICP has been lacking. This paper aims to bridge this gap by providing a systematic way to generate effective extended formulations for a broad class of MICP problems.

Methods

The core of this paper lies in two main contributions:

  • Conic Representability: The authors show that a vast majority of MICP instances, even those not immediately obvious, can be represented using standard conic forms (second-order cones, exponential cones, and power cones). This is a significant finding, as conic optimization has well-developed theory and solvers. The key insight is that these conic representations are themselves effective extended formulations, naturally encoding separability and other structures.
  • A Unifying Framework for Extended Formulations: The paper proposes a general framework for generating extended formulations for MICP. This framework leverages the conic representability and also connects to the Disciplined Convex Programming (DCP) modeling paradigm. DCP provides a set of rules for constructing convex expressions, and the authors show a direct correspondence between these rules and the existence of extended formulations. This means that any problem formulated in DCP automatically has an extended formulation, regardless of whether it's conic representable.
  • A Novel Outer Approximation Algorithm: Building on the conic representation, the authors present the first finite-time outer approximation algorithm specifically designed for mixed-integer conic programming problems with arbitrary closed, convex cones. This algorithm is a generalization of existing methods for MISOCP and offers a more robust approach to solving these problems.

Datasets

The primary dataset used for evaluation is the MINLPLIB2 benchmark library. The authors classify the instances within this library based on their conic representability (e.g., SOC only, EXP only, SOC and EXP). They also highlight specific instances like "trimloss" and "gams01" as challenging examples that were previously unsolved.

Key Insights and Ideas

  • Conic Forms as Extended Formulations: The paper reveals that reformulating MICP problems into conic forms is not just a way to leverage conic solvers, but it inherently creates powerful extended formulations. This is a crucial conceptual shift.
  • DCP as a Gateway to Extended Formulations: The connection between DCP's composition rules and the existence of extended formulations is a key insight. It suggests that users of DCP are implicitly generating problems with built-in extended formulations, even if they aren't aware of it.
  • Ubiquity of Conic Representability: The finding that nearly all MICP instances in MINLPLIB2 are conic representable is surprising and suggests that conic optimization might be more broadly applicable to MICP than previously thought.
  • Solving Previously Unsolved Problems: The ability to solve challenging instances like "gams01" and "trimloss" demonstrates the practical power of their approach.

Key Results

  • Conic Representability: All 333 MICP instances in the MINLPLIB2 benchmark library were found to be conic representable using standard cones (second-order, exponential, and power cones). Over two-thirds were pure MISOCP, and nearly one-third required the exponential cone.
  • Performance Improvements: The proposed extended formulations significantly reduced the number of outer approximation iterations.
  • Solving Open Instances: The authors successfully solved previously unsolved instances from MINLPLIB2, such as "gams01" and "trimloss," by reformulating them into conic forms. For "gams01," their solver Pajarito achieved optimality with a significantly improved objective value.
  • New Algorithm: The paper presents the first finite-time outer approximation algorithm for general mixed-integer conic programming.

Limitations and Future Work

  • Solver Reliability: While conic forms are powerful, the authors note that the development of reliable solvers for nonsymmetric cones (like exponential and power cones) is still an active research area. Their implementation of the outer approximation algorithm relies on derivative-based NLP solvers for continuous relaxations due to the current limitations of conic solvers.
  • Algorithm Assumptions: The presented outer approximation algorithm relies on assumptions (like strong duality) that may not always hold. The authors acknowledge that further work is needed to address these cases, drawing parallels to existing procedures for MISOCP.
  • Generalization of Cones: The algorithm is presented for a single cone K for simplicity, but the authors mention that their implementation disaggregates elements of K* for product cones, suggesting a path for handling more complex conic structures.
  • Broader Applicability: While the paper focuses on MICP, the connection to DCP suggests potential applications to a wider range of convex optimization problems. Future work could explore this further.

Summary updated

BibTeX
@inproceedings{lubin2016extended,
  author = {Miles Lubin and Emre Yamangil and Russell Bent and Juan Pablo Vielma},
  title = {{Extended Formulations in Mixed-Integer Convex Programming}},
  booktitle = {IPCO},
  year = {2016},
  doi = {10.1007/978-3-319-33461-5\_9},
}
Figure