quadprogIP
Globally solving nonconvex quadratic programs via linear integer programming techniques . We reformulate a (indefinite) quadratic program (QP) as a mixed-integer linear programming (MILP) problem by first reformulating a QP as a linear complementary problem, and then using binary variables and big-M constraints to model its complementary constraints. To obtain such reformulation, we use fundamental results on the solution of perturbed linear systems to impose bounds on the QP’s dual variables without eliminating any of its (globally) optimal primal solutions. Reformulating a nonconvex QP as a MILP problem allows the use of current state-of-the-art MILP solvers to find its global optimal solution. To illustrate this, we compare the performance of this MILP-based solution approach, labeled quadprogIP, with quadprogBB, BARON, and CPLEX. In practice, quadprogIP is shown to typically outperform by orders of magnitude quadprogBB, BARON, and CPLEX on standard QPs. Also, unlike quadprogBB, quadprogIP is able to solve QP instances in which the dual feasible set is unbounded. The MATLAB code quadprogIP and the instances used to perform the reported numerical experiments are publicly available at url{https://github.com/xiawei918/quadprogIP}.
Keywords for this software
References in zbMATH (referenced in 7 articles , 1 standard article )
Showing results 1 to 7 of 7.
Sorted by year (- Anstreicher, Kurt M.: Testing copositivity via mixed-integer linear programming (2021)
- Fampa, Marcia; Lee, Jon: Convexification of bilinear forms through non-symmetric lifting (2021)
- Gondzio, Jacek; Yıldırım, E. Alper: Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations (2021)
- Liuzzi, G.; Locatelli, M.; Piccialli, V.; Rass, S.: Computing mixed strategies equilibria in presence of switching costs by the solution of nonconvex QP problems (2021)
- Bienstock, Daniel; Chen, Chen; Muñoz, Gonzalo: Outer-product-free sets for polynomial optimization and oracle-based cuts (2020)
- Gourtani, Arash; Nguyen, Tri-Dung; Xu, Huifu: A distributionally robust optimization approach for two-stage facility location problems (2020)
- Xia, Wei; Vera, Juan C.; Zuluaga, Luis F.: Globally solving nonconvex quadratic programs via linear integer programming techniques (2020)