Fix and Bound: An efficient approach for solving large-scale quadratic programming problems with box constraints

Abstract

In this paper, we propose a branch-and-bound algorithm for solving nonconvex quadratic programming problems with box constraints (BoxQP). Our approach combines 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.

References in corpus (7)

• SOS-SDP: an Exact Solver for Minimum Sum-of-Squares Clustering
• A Semidefinite Programming Method for Integer Convex Quadratic Minimization
• Global Solutions of Nonconvex Standard Quadratic Programs via Mixed Integer Linear Programming Reformulations
• BiqBin: a parallel branch-and-bound solver for binary quadratic problems with linear constraints
• An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering
• Global Optimization for Cardinality-constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming
• Improving ADMMs for Solving Doubly Nonnegative Programs through Dual Factorization

Cited by in corpus (1)

• Exact and Heuristic Algorithms for Constrained Biclustering