A Grid-enabled Branch and Bound Algorithm for Solving Challenging Combinatorial Optimization Problems

Solving optimally large instances of combinatorial op-timization problems requires a huge amount of computa-tional resources. In this paper, we propose an adaptation of the parallel Branch and Bound algorithm for computa-tional grids. Such gridification is based on new ways to efficiently deal with some crucial issues, mainly dynamic adaptive load balancing, fault tolerance, global informa-tion sharing and termination detection of the algorithm. A new efficient coding of the work units (search sub-trees) dis-tributed during the exploration of the search tree is pro-posed to optimize the involved communications. The al-gorithm has been implemented following a large scale idle time stealing paradigm (Farmer-Worker). It has been exper-imented on a Flow-Shop problem instance ( ) that has never been optimally solved. The new algorithm allowed to realize a success story as the optimal solution has been found with proof of optimality, within days using about processors belonging to Nation-wide distinct clus-ters (administration domains). During the resolution, the worker processors were exploited with an average of while the farmer processor was exploited only of the time. These two rates are good indicators on the efficiency of the proposed approach and its scalability