Numerical Experience with Lower Bounds for MIQP Branch-And-Bound

TLDR

Convex mixed‑integer quadratic programming problems are addressed within a general branch‑and‑bound framework. The authors present an efficient technique for computing lower bounds during the branch‑and‑bound process. These improved bounds reduce the number of quadratic‑programming subproblems, and numerical experiments show the branch‑and‑bound approach outperforms other methods for MIQP.

Abstract

The solution of convex mixed-integer quadratic programming (MIQP) problems with a general branch-and-bound framework is considered. It is shown how lower bounds can be computed efficiently during the branch-and-bound process. Improved lower bounds such as the ones derived in this paper can reduce the number of quadratic programming (QP) problems that have to be solved. The branch-and-bound approach is also shown to be superior to other approaches in solving MIQP problems. Numerical experience is presented which supports these conclusions.