Solving the three dimensional quadratic assignment problem on a computational grid

Abstract : The exact resolution of large instances of combinatorial optimization problems, such as three dimensional quadratic assignment problem (Q3AP), is a real challenge for grid computing. Indeed, it is necessary to reconsider the resolution algorithms and take into account the characteristics of such environments, especially large scale and dynamic availability of resources, and their multi-domain administration.In this paper, we revisit the design and implementation of the branch and bound algorithm for solving large combinatorial optimization problems such as Q3AP on the computational grids. Such gridification is based on new ways to efficiently deal with some crucial issues, mainly dynamic adaptive load balancing and fault tolerance. Our new approach allowed the exact resolution on a nation-wide grid of a difficult Q3AP instance. To solve this instance, an average of 1,123 computing cores were used for less than 12 days with a peak of around 3,427 computing cores.
Type de document :
Article dans une revue
Journal of Cluster Computing, Springer, 2014, 17 (2), pp.13. 〈10.1007/s10586-013-0313-4〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01095464
Contributeur : Nouredine Melab <>
Soumis le : lundi 15 décembre 2014 - 16:11:45
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13

Identifiants

Citation

Mohand Mezmaz, Malika Mehdi, Pascal Bouvry, Nouredine Melab, El-Ghazali Talbi, et al.. Solving the three dimensional quadratic assignment problem on a computational grid. Journal of Cluster Computing, Springer, 2014, 17 (2), pp.13. 〈10.1007/s10586-013-0313-4〉. 〈hal-01095464〉

Partager

Métriques

Consultations de la notice

209