Branch-and-Bound (B&B) is a frequently used tree-search exploratory method for the exact resolution of combinatorial optimization problems (COPs). However, in practice, only small problem instances can be solved on a sequential computer, as B&B generates often generates a huge amount of subproblems to be evaluated. In order to solve large COPs, we revisit the design and implementation of massively parallel B&B on top of large heterogeneous clusters, integrating multi-core CPUs, many-core processors and GPUs. For the efficient storage and management of subproblems an original data structure (IVM) dedicated to permutation problems is used. Because of the highly irregular and unpredictable shape of the B&B tree, dynamic load balancing between parallel exploration processes is one of the main issues addressed in this thesis. Based on a compact encoding of the search space in the form of intervals, work stealing strategies for multi-core and GPU are proposed, as well as hierarchical approaches for load balancing in distributed memory multi-CPU/multi-GPU systems. Three permutation problems, the Flowshop Scheduling Problem (FSP), the Quadratic Assignment Problem (QAP) and the n-Queens puzzle problem are used as test-cases. The resolution, in 9 hours, of a FSP instance with an estimated sequential execution time of 22 years demonstrates the scalability of the proposed algorithms on a cluster composed of 36 GPUs.
Directeurs de thèse : Melab, Nouredine (Université de Lille) Tuyttens, Daniel (UMONS) Mezmaz, Mohand (UMONS) Rapporteurs : Cappello, Franck (Argonne National Laboratory) Yalaoui, Farouk (Université de Technologies Troyes) Examinateurs : Stolf, Patricia (Université Toulouse) Mannebeck, Pierre (UMONS) Chakroun, Imen (IMEC) Jaszkiewicz, Andrzej (University of Technology Poznan) Semet, Frédéric (Ecole Centrale Lille)
Thesis of the team BONUS defended on 19/12/2017
français
English