A parallel branch and bound algorithm for multicomputer systems

Branch-and-bound algorithms are used to solve a high number of important optimization problems. The class of complexity of such problems is of the type NP; in most practical cases, their solution requires a large amount of computing resources. Parallelization of the branch-and-bound techniques is quite promising in order to reduce computing time and improve the size of maximum tractable problems. The problems arising in parallelization depends on the class of architectures used. Among these, multicomputeres appear to be a very interesting category, due to their increasing use. A multicomputer consists of many independent units that communicate by exchanging messages through a local net. In this paper an approach to parallelization of branch-and-bound algorithms is proposed for multicomputer systems, based on CSP. Some results of experiments made in distributed environments (DISC and PVM) are presented.