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

Mohand Mezmaz 1 Nouredine Melab 2 El-Ghazali Talbi 2
2 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : Solving optimally large 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. Such gridification is based on 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 new efficient coding of the work units (search sub-trees) distributed during the exploration of the search tree is proposed to optimize the involved communications. The algorithm has been implemented following a large scale idle time stealing paradigm (Farmer-Worker). It has been experimented 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 clusters (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.
Type de document :
Communication dans un congrès
IEEE International Parallel and Distributed Processing Symposium, 2007. IPDPS 2007., Mar 2007, Long Beach, CA, United States. 2007
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00841951
Contributeur : Nouredine Melab <>
Soumis le : vendredi 5 juillet 2013 - 17:57:05
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : dimanche 6 octobre 2013 - 04:18:01

Fichier

04227945.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00841951, version 1

Citation

Mohand Mezmaz, Nouredine Melab, El-Ghazali Talbi. A Grid-enabled Branch and Bound Algorithm for Solving Challenging Combinatorial Optimization Problems. IEEE International Parallel and Distributed Processing Symposium, 2007. IPDPS 2007., Mar 2007, Long Beach, CA, United States. 2007. 〈hal-00841951〉

Partager

Métriques

Consultations de la notice

561

Téléchargements de fichiers

143