A dual bounding framework for binary quadratic combinatorial optimization

, , , and

BibTeX reference

Binary quadratic programming (BQP) is a class of combinatorial optimization problems comprising binary variables, quadratic objective functions and linear/non-linear constraints. In this paper, we propose a unified framework to reformulate any BQP problem with linear constraints to a new BQP problem defined on a graph. This framework relies on the concept of stars in the graph and partitioning the quadratic costs into in-star and out-of-star interactions. We exploit the star-based structure of the new reformulation to develop a decomposition-based column generation algorithm. In our computational experiments, we evaluate the performance of our methodology on different applications with different quadratic structures in which the quadratic component of the problem is dealt with in the column generation master problem and in its subproblem. Results suggest that the framework outperforms the state-of-the-art solver in almost all the instances having zero out-of-star interactions both in terms of dual bound and computational time.

, 42 pages

Research Axis

Research application


G2143.pdf (700 KB)