Fix and bound: an efficient approach for solving large-scale quadratic programming problems with box constraints
- In this paper, we propose a branch-and-bound algorithm for solving nonconvex
quadratic programming problems with box constraints (BoxQP). Our approach com-
bines existing tools, such as semidefinite programming (SDP) bounds strengthened
through valid inequalities, with a new class of optimality-based linear cuts which leads
to variable fixing. The most important effect of fixing the value of some variables is
the size reduction along the branch-and-bound tree, allowing to compute bounds by
solving SDPs of smaller dimension. Extensive computational experiments over large
dimensional (up to n = 200) test instances show that our method is the state-of-the-art
solver on large-scale BoxQPs. Furthermore, we test the proposed approach on the class
of binary QP problems, where it exhibits competitive performance with state-of-the-art
solvers.