A Multi-Core Parallel Branch-and-Bound Algorithm Using Factorial Number System

Mohand Mezmaz 1 Rudi Leroy 2 Nouredine Melab 2 Daniel Tuyttens 1
2 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : Many real-world problems in different industrial and economic fields are permutation combinatorial optimization problems. Solving to optimality large instances of these problems, such as flowshop problem, is a challenge for multi-core computing. This paper proposes a multi-threaded factoradic-based branch-and-bound algorithm to solve permutation combinatorial problems on multi-core processors. The factoradic, called also factorial number system, is a mixed radix numeral system adapted to numbering permutations. In this new parallel algorithm, the B&B is based on a matrix of integers instead of a pool of permutations, and work units exchanged between threads are intervals of factoradics instead of sets of nodes. Compared to a conventional pool-based approach, the obtained results on flowshop instances demonstrate that our new factoradic-based approach, on average, uses about 60 times less memory to store the pool of subproblems, generates about 1.3 times less page faults, waits about 7 times less time to synchronize the access to the pool, requires about 9 times less CPU time to manage this pool, and performs about 30,000 times less context switches.
Type de document :
Communication dans un congrès
IPDPS 2014 : 28th IEEE International Parallel & Distributed Processing Symposium, May 2014, Phoenix (Arizona), United States. IEEE, 2014, 〈10.1109/IPDPS.2014.124〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00934841
Contributeur : Nouredine Melab <>
Soumis le : mercredi 22 janvier 2014 - 16:17:30
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13

Identifiants

Citation

Mohand Mezmaz, Rudi Leroy, Nouredine Melab, Daniel Tuyttens. A Multi-Core Parallel Branch-and-Bound Algorithm Using Factorial Number System. IPDPS 2014 : 28th IEEE International Parallel & Distributed Processing Symposium, May 2014, Phoenix (Arizona), United States. IEEE, 2014, 〈10.1109/IPDPS.2014.124〉. 〈hal-00934841〉

Partager

Métriques

Consultations de la notice

373