Extended formulations in mixed integer conic quadratic programming.

Juan Pablo Vielma, Iain Dunning, Joey Huchette, Miles LubinMath. Program. Comput 2017 · OpenReview

TL;DR

This paper introduces a new way to reformulate mixed integer conic quadratic programming (MICQP) problems using "extended formulations." These new formulations, derived from a homogenization technique, significantly improve the performance of existing LP-based solvers, offering an easy-to-implement approach that speeds up solving complex optimization problems.

What Problem Does This Paper Address?

Solving mixed integer conic quadratic programming (MICQP) problems is a challenging task in optimization. Traditional approaches often rely on solving expensive nonlinear relaxations within a branch-and-bound framework. While some methods use "extended formulations" (adding auxiliary variables to create simpler, yet equivalent, relaxations), existing techniques have limitations. One approach, while efficient, has a fixed approximation quality that can't be improved. Another, which can be improved, is restricted to problems with convex quadratic constraints. This paper aims to bridge this gap by developing an extended formulation that works for general MICQP problems and can be iteratively refined, offering a better balance of efficiency and adaptability.

Methods

The core contribution is a novel extended formulation for MICQP problems. This is achieved by:

  • Homogenization: Adapting a technique originally used for the Euclidean ball to the Lorentz cone, which is fundamental to conic quadratic programming.
  • Combining Techniques: Merging the homogenization approach with techniques from Tawarmalani and Sahinidis (which allow for iterative refinement of approximations) and Hijazi, Bonami, and Ouorou (which provide a specific type of lifted relaxation).
  • Dynamic Lifted Polyhedral Relaxations: The resulting formulations are "dynamic" because their approximation quality can be improved iteratively, unlike "static" relaxations.
  • Algorithm Adaptation: These new formulations are integrated into existing LP-based branch-and-bound algorithms, either by directly using them as reformulations or by adapting the LiftedLP algorithm.

Datasets

The authors evaluated their methods on portfolio optimization instances from a previous study [45]. These instances fall into three classes:

  • Classical: Standard portfolio optimization with diversification or cardinality constraints.
  • Shortfall: Similar to classical but with a "shortfall constraint."
  • Robust: A version that includes an additional continuous variable and modifies the objective function.

The instances were generated with varying numbers of assets ($n \in \{10, 20, 30, 40, 50, 60, 100, 200, 300\}$) and portfolio sizes ($K=10$). For each problem class and $n$, 100 randomly generated instances were tested.

Key Insights and Ideas

  • Bridging the Gap: The paper successfully adapts a powerful, iteratively refinable relaxation technique (originally for Euclidean balls) to the Lorentz cone, making it applicable to a broader class of MICQP problems.
  • Homogenization is Key: The homogenization procedure is the crucial step that allows the adaptation of existing techniques to handle general MICQP problems, not just those with convex quadratic constraints.
  • Dynamic Relaxations Offer Flexibility: The ability to iteratively refine the approximation quality of the lifted polyhedral relaxations is a significant advantage over static approaches, allowing for better trade-offs between solution time and accuracy.
  • Practical Performance Gains: The new formulations, particularly the "separable" one, demonstrate substantial performance improvements over traditional LP-based and NLP-based algorithms, and even over the original LiftedLP algorithm.

Key Results

The computational experiments showed that the proposed extended formulations, especially the "separable" dynamic lifted polyhedral relaxation, significantly improved the performance of LP-based algorithms for MICQP problems.

  • Speedup: The separable reformulation consistently outperformed other dynamic lifted relaxations and traditional LP/NLP-based algorithms. For instance, in the "Shortfall" instances with $n=20$, the separable relaxation was the fastest option in 54 out of 100 cases.
  • Solver Performance: Both CPLEX and Gurobi solvers benefited from the new formulations, with GurobiSepLP and CPLEXSepLP often showing the best performance.
  • Solution Quality: While the separable reformulation sometimes led to a slight reduction in feasibility quality for conic constraints, this was easily resolvable by increasing precision or correcting solutions.
  • Cut-based vs. Branch-based: The cut-based LiftedLP algorithm, which leverages the dynamic relaxations, showed comparable or better performance than the original branch-based LiftedLP, and was easier to implement.

Limitations and Future Work

  • Approximation Quality: The paper raises open questions about the theoretical limits of approximation quality for dynamic lifted polyhedral relaxations, specifically for the "tower of variables" and "separable" types. Determining the smallest possible size for a given approximation quality remains an area for future research.
  • Generalizing Q¹/²: The improvement in formulation strengthening for portfolio optimization was shown for $Q^{1/2} = I$. Extending this to general $Q^{1/2}$ might be possible using other known techniques.
  • Implementation Details: The authors note that while their JuMP implementation of cut-based LiftedLP is flexible, direct solver integration might offer further advantages by avoiding potential interference with solver's internal features.

Summary updated

Abstract

In this paper we consider the use of extended formulations in LP-based algorithms for mixed integer conic quadratic programming (MICQP). Extended formulations have been used by Vielma et al. (INFORMS J Comput 20: 438–450, 2008) and Hijazi et al. (Comput Optim Appl 52: 537–558, 2012) to construct algorithms for MICQP that can provide a significant computational advantage. The first approach is based on an extended or lifted polyhedral relaxation of the Lorentz cone by Ben-Tal and Nemirovski (Math Oper Res 26(2): 193–205 2001) that is extremely economical, but whose approximation quality cannot be iteratively improved. The second is based on a lifted polyhedral relaxation of the euclidean ball that can be constructed using techniques introduced by Tawarmalani and Sahinidis (Math Programm 103(2): 225–249, 2005). This relaxation is less economical, but its approximation quality can be iteratively improved. Unfortunately, while the approach of Vielma, Ahmed and Nemhauser is applicable for general MICQP problems, the approach of Hijazi, Bonami and Ouorou can only be used for MICQP problems with convex quadratic constraints. In this paper we show how a homogenization procedure can be combined with the technique by Tawarmalani and Sahinidis to adapt the extended formulation used by Hijazi, Bonami and Ouorou to a class of conic mixed integer programming problems that include general MICQP problems. We then compare the effectiveness of this new extended formulation against traditional and extended formulation-based algorithms for MICQP. We find that this new formulation can be used to improve various LP-based algorithms. In particular, the formulation provides an easy-to-implement procedure that, in our benchmarks, significantly improved the performance of commercial MICQP solvers.
BibTeX
@inproceedings{vielma2017extended,
  author = {Juan Pablo Vielma and Iain Dunning and Joey Huchette and Miles Lubin},
  title = {{Extended formulations in mixed integer conic quadratic programming.}},
  booktitle = {Math. Program. Comput},
  year = {2017},
  url = {https://openreview.net/forum?id=MgeNiBqajk0},
}
Figure