Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadatas

https://hal.inria.fr/hal-00934841
Contributor : Nouredine Melab <>
Submitted on : Wednesday, January 22, 2014 - 4:17:30 PM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM

Identifiers

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, Manish Parashar (Rutgers University, USA), May 2014, Phoenix (Arizona), United States. ⟨10.1109/IPDPS.2014.124⟩. ⟨hal-00934841⟩

Share

Metrics

Record views

483