A heuristic-based branch and bound algorithm for unconstrained quadratic zero-one programming (Q1893147)

This paper describes a branch and bound algorithm for solving the unconstrained quadratic 0-1 programming problem. The salient features of it are the use of quadratic programming heuristics in the transformation of subproblems and exploiting some classes of facets of the polytope related to the quadratic problem in deriving upper bounds on the objective function. The authors develop facet selection procedures that form a basis of the bound computation algorithm and present computational experience on four series of randomly generated problems and 14 real instances of a quadratic problem arising in design automation. Moreover, the same ideas can also be applied to some other combinatorial optimization problems.