Parallel branch and bound algorithms for quadratic zero–one programs on the hypercube architecture

We present a parallel branch and bound algorithm for unconstrained quadratic zero-one programs on the hypercube architecture. Subproblems parallelize well without the need of a shared data structure to store expanded nodes of the search tree. Load balancing is achieved by demand splitting of neighboring subproblems. Computational results on a variety of large-scale problems are reported on an iPSC/1 32-node hypercube and an iPSC/2 16-node hypercube.