Abstract
The class of mixed-integer quadratically constrained quadratic programs (QCQP) consists of minimizing a quadratic function under quadratic constraints where the variables could be integer or continuous. On a previous paper we introduced a method called MIQCR for solving QCQPs with the following restriction: all quadratic sub-functions of purely continuous variables are already convex. In this paper, we propose an extension of MIQCR which applies to any QCQP. Let be a QCQP. Our approach to solve
is first to build an equivalent mixed-integer quadratic problem
. This equivalent problem
has a quadratic convex objective function, linear constraints, and additional variables y that are meant to satisfy the additional quadratic constraints
, where x are the initial variables of problem
. We then propose to solve
by a branch-and-bound algorithm based on the relaxation of the additional quadratic constraints and of the integrality constraints. This type of branching is known as spatial branch-and-bound. Computational experiences are carried out on a total of 325 instances. The results show that the solution time of most of the considered instances is improved by our method in comparison with the recent implementation of QuadProgBB, and with the solvers Cplex, Couenne, Scip, BARON and
GloMIQO.
Acknowledgements
The authors are grateful to Alain Billionnet for all our collaborations and for a careful reading of this manuscript.
Disclosure statement
No potential conflict of interest was reported by the authors.
Supplemental data
Supplemental data for this article can be accessed at https://doi.org/10.1080/10556788.2017.1350675.