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