Skip to Main content Skip to Navigation
Journal articles

Peer-to-peer design and implementation of a parallel branch and bound algorithm for grids

Abstract : Solving optimally large instances of combinatorial optimisation problems using Branch and Bound (B&B) algorithms is CPU-time intensive and requires a large number of computational resources. To harness such huge amount of resources Peer-to-Peer (P2P) communications must be allowed between resources, and adaptive load balancing and fault-tolerance have to be dealt with when designing and implementing a B&B algorithm. In this paper, we propose a P2P design and implementation of a parallel B&B algorithm on top of the ProActive grid middleware. Load distribution and fault-tolerance strategies are proposed to deal with the dynamic and heterogeneous characteristics of the computational grid. The approach has been promisingly applied to the Flow-Shop scheduling problem and experimented on a computational pool of 1500 CPUs from the GRID|5000 Nation-wide experimental Grid.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-00836756
Contributor : Talbi El-Ghazali <>
Submitted on : Friday, June 21, 2013 - 2:41:51 PM
Last modification on : Thursday, April 8, 2021 - 9:04:42 AM

Identifiers

Citation

Ahcène Bendjoudi, Nouredine Melab, El-Ghazali Talbi. Peer-to-peer design and implementation of a parallel branch and bound algorithm for grids. International Journal of Grid and Utility Computing, Inderscience, 2009, 1 (2), pp.159-168. ⟨10.1504/IJGUC.2009.022031⟩. ⟨hal-00836756⟩

Share

Metrics

Record views

243