The ‘roof dual’ of a QUBO (Quadratic Unconstrained Binary Optimization) problem has been introduced by Hammer et al.; it provides a bound to the optimum value, along with a polynomial test of the sharpness of this bound, and (due to a ‘persistency’ result) it also determines the values of some of the variables at the optimum. In this paper we provide a graph–theoretic approach to provide bounds, which includes as a special case the roof dual bound, and show that these bounds can be computed in O(n3) time by using network flow techniques. We also obtain a decomposition theorem for quadratic pseudo-Boolean functions, improving the persistency result of that paper. Finally, we show that the proposed bounds (including roof duality) can be applied in an iterated way to obtain significantly better bounds. Computational experiments on problems up to thousands of variables are presented.
