• English
    • français
  • Help
  •  | 
  • Contact
  •  | 
  • About
  •  | 
  • Login
  • HAL portal
  •  | 
  • Pages Pro
  • EN
  •  / 
  • FR
View Item 
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

A Grid-enabled Branch and Bound Algorithm ...
  • BibTeX
  • CSV
  • Excel
  • RIS

Document type :
Rapport de recherche
Title :
A Grid-enabled Branch and Bound Algorithm for Solving Challenging Combinatorial Optimization Problems
Author(s) :
Mezmaz, Mohand [Auteur]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Melab, Nouredine [Auteur] refId
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Talbi, El-Ghazali [Auteur] refId
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Institution :
INRIA
Publication date :
2006
English keyword(s) :
Branch and Bound
Parallel Computing
Grid Computing
Flow-Shop Problem
Performance Evaluation
HAL domain(s) :
Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
English abstract : [en]
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 ...
Show more >
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.Show less >
Language :
Anglais
Collections :
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Source :
Harvested from HAL
Files
Thumbnail
  • https://hal.inria.fr/inria-00083814v2/document
  • Open access
  • Access the document
Thumbnail
  • https://hal.inria.fr/inria-00083814v2/document
  • Open access
  • Access the document
Thumbnail
  • https://hal.inria.fr/inria-00083814v2/document
  • Open access
  • Access the document
Université de Lille

Mentions légales
Université de Lille © 2017