Experimental evaluation of node-variable selection rules in PC cluster-based parallel branch-and-bound algorithms

摘要

A branch-and-bound algorithm (BB for short) is the most general technique to deal with various combinatorial optimization problems. Even if it is used, the computation time is likely to increase exponentially. So we consider its parallelization to reduce it. It has been reported, through experimentation on transputers networks, that the computation time of a parallel BB heavily depends upon node-variable selection strategies. In this paper, we experimentally evaluate how node-variable selection strategies affect the computation time of a parallel BB on a PC cluster.