Parallel Branch and Bound Algorithms on Hypercube Multiprocessors*

Branch and Bound (BB) algorithms are a generalization of many search algorithms used in Artificial Intelligence and Operations Research. This paper presents our work on imple-menting BB algorithms on hypercube multiprocessors. The O-l integer linear programming (ILP) problem is taken as an example because it can be implemented to capture the essence of BB search algorithms without too many distract-ing problem specific details. A BB algorithm for the &l ILP problem is discussed. Two parallel implementations of the algorithm on hypercube multiprocessors are presented. The two implementations demonstrate some of the tradeoffs in-volved in implementing these algorithms on multiprocessors with no shared memory, su.ch as hypercubes. Experimental results from the NCUBE/six show the performance of the two implementations of the algorithm. Future research work is discussed.