Improving a Lagrangian decomposition for the unconstrained binary quadratic programming problem

This paper presents a new alternative of Lagrangian decomposition based on column generation technique to solve the unconstrained binary quadratic programming problem. We use a mixed binary linear version of the original quadratic problem with constraints represented by a graph. This graph is partitioned into clusters of vertices forming subproblems whose solutions use the dual variables obtained by a coordinator problem. Computational experiments consider a set of difficult instances and the results are compared against other methods reported recently in the literature.