Using general triangle inequalities within quadratic convex reformulation method
- 16 January 2023
- journal article
- research article
- Published by Taylor & Francis in Optimization Methods and Software
- Vol. 38 (3) , 626-653
Abstract
We consider the exact solution of Problem (P) which consists in minimizing a quadratic function subject to quadratic constraints. We start with an explicit description of new general triangle inequalities that are derived from the ranges of the variables of (P). We show that they extend the triangle inequalities, introduced for the binary case, to variables that belong to a generic interval. We also prove that these inequalities cut feasible solutions of McCormick envelopes, and we relate them to the literature. We then introduce (SDP), a strong semidefinite relaxation of (P), that we call ‘Shor's plus RLT plus Triangle’, which includes both the McCormick envelopes and the general triangle inequalities. We further show how to compute a convex relaxation whose optimal value reaches the value of (SDP). In order to handle these inequalities in the solution of (SDP), we solve it by a heuristic that also serves as a separation algorithm. We then solve (P) to global optimality with a branch-and-bound based on . Finally, we show that our method outperforms the compared solvers.
Keywords
This publication has 31 references indexed in Scilit:
- Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxationsMathematical Programming, 2012
- Extending the QCR method to general mixed-integer programsMathematical Programming, 2010
- Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-boundComputational Optimization and Applications, 2007
- A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxationsMathematical Programming, 2006
- On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programmingMathematical Programming, 2005
- A polyhedral study of nonconvex quadratic programs with box constraintsMathematical Programming, 2004
- Benchmarking optimization software with performance profilesMathematical Programming, 2002
- CSDP, A C library for semidefinite programmingOptimization Methods and Software, 1999
- GLOBAL OPTIMIZATION ALGORITHMS FOR CHIP LAYOUT AND COMPACTIONEngineering Optimization, 1995
- Quadratically constrained quadratic programming: Some applications and a method for solutionMathematical Methods of Operations Research, 1982