HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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

Mohand Mezmaz 1 Nouredine Melab 1 El-Ghazali Talbi 1
1 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : Solving exactly large scale instances of combinatorial optimization problems requires a huge amount of computational resources. In this paper, we propose an adaptation of the parallel Branch and Bound algorithm for computational grids. We consequently propose new ways to efficiently deal with some crucial issues, mainly dynamic adaptive load balancing, fault tolerance, global information sharing and termination detection of the algorithm. A special coding of the work units distributed and folded/unfolded during the exploration of the search tree allows to optimize the involved communications. The algorithm has been implemented following a large scale idle time stealing paradigm. It has been experimented on a Flow-Shop problem instance (Ta056) that has never been solved exactly. The optimal solution has been found with proof of optimality within 25 days using about 1900 processors belonging to 9 Nation-wide distinct clusters (administration domains). During the resolution, the worker processors were exploited with an average to 97% while the farmer processor was exploited only 1.7% of the time. These two rates are good indicators on the parallel efficiency of the proposed approach and its scalability.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, July 7, 2006 - 10:42:44 AM
Last modification on : Thursday, January 20, 2022 - 5:27:52 PM
Long-term archiving on: : Monday, September 20, 2010 - 4:23:57 PM


  • HAL Id : inria-00083814, version 2


Mohand Mezmaz, Nouredine Melab, El-Ghazali Talbi. A Grid-enabled Branch and Bound Algorithm for Solving Challenging Combinatorial Optimization Problems. [Research Report] INRIA. 2006, pp.15. ⟨inria-00083814v2⟩



Record views


Files downloads