Article: P2P computing for large tree exploration-based exact optimisation Journal: International Journal of Grid and Utility Computing (IJGUC) 2009 Vol.1 No.3 pp.252 - 260 Abstract: The Branch and Bound (B&B) algorithm is one of the most used methods to solve in an exact way combinatorial optimisation problems. In a previous article, we proposed a new approach of the parallel B&B algorithm for distributed systems using the farmer-worker paradigm. However, the new farmer-worker approach has a disadvantage: some nodes of the B&B tree can be explored by several B&B processes. To prevent this redundant work and speed up, we propose a new P2P approach inspired from the strategies of existing P2P systems like Napster and JXTA. Validation is performed by experimenting the two approaches on mono-objective flow-shop problem benchmarks using 500 processors belonging to the French national grid, Grid|5000. The obtained results prove the efficiency of the proposed P2P approach. Indeed, the execution time obtained with the P2P version, even if more communicative, is better than the farmer-worker|s one. Inderscience Publishers - linking academia, business and industry through research

Title: P2P computing for large tree exploration-based exact optimisation

Authors: M. Mehdi, M. Mezmaz, N. Melab, E-G. Talbi, P. Bouvry

Addresses: Faculty of Sciences, Technology and Communication, University of Luxembourg, 6 rue Coudenhove Kalergi, L-1359, Luxembourg, Luxembourg. ' INRIA Lille-Nord Europe, Parc Scientifique de la Haute Borne, 40, avenue Halley, Bt. A, Park Plaza, 59650 Villeneuve d'Ascq, France. ' INRIA Lille-Nord Europe, Parc Scientifique de la Haute Borne, 40, avenue Halley, Bt. A, Park Plaza, 59650 Villeneuve d'Ascq, France. ' INRIA Lille-Nord Europe, Parc Scientifique de la Haute Borne, 40, avenue Halley, Bt. A, Park Plaza, 59650 Villeneuve d'Ascq, France. ' Faculty of Sciences, Technology and Communication, University of Luxembourg, 6 rue Coudenhove Kalergi, L-1359, Luxembourg, Luxembourg

Abstract: The Branch and Bound (B&B) algorithm is one of the most used methods to solve in an exact way combinatorial optimisation problems. In a previous article, we proposed a new approach of the parallel B&B algorithm for distributed systems using the farmer-worker paradigm. However, the new farmer-worker approach has a disadvantage: some nodes of the B&B tree can be explored by several B&B processes. To prevent this redundant work and speed up, we propose a new P2P approach inspired from the strategies of existing P2P systems like Napster and JXTA. Validation is performed by experimenting the two approaches on mono-objective flow-shop problem benchmarks using 500 processors belonging to the French national grid, Grid|5000. The obtained results prove the efficiency of the proposed P2P approach. Indeed, the execution time obtained with the P2P version, even if more communicative, is better than the farmer-worker|s one.

Keywords: P2P computing; peer-to-peer; exact optimisation; flow shop scheduling; branch and bound algorithms; parallel exploration; load balancing; fault tolerance.

DOI: 10.1504/IJGUC.2009.027652

International Journal of Grid and Utility Computing, 2009 Vol.1 No.3, pp.252 - 260

Published online: 05 Aug 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article

Title: P2P computing for large tree exploration-based exact optimisation

Keep up-to-date