Skip to Main content Skip to Navigation

Heterogeneous cluster computing for many-task exact optimization - Application to permutation problems

Jan Gmys 1, 2, 3
Abstract : 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.
Complete list of metadata
Contributor : Jan Gmys Connect in order to contact the contributor
Submitted on : Wednesday, November 29, 2017 - 6:09:18 PM
Last modification on : Friday, December 11, 2020 - 6:44:05 PM


Files produced by the author(s)


  • HAL Id : tel-01652000, version 1


Jan Gmys. Heterogeneous cluster computing for many-task exact optimization - Application to permutation problems. Distributed, Parallel, and Cluster Computing [cs.DC]. Université de Mons (UMONS); Université de Lille, 2017. English. ⟨tel-01652000⟩



Record views


Files downloads