Contribution à la résolution de problèmes d'optimisation combinatoire : méthodes séquentielles et parallèles
Mohamed Esseghir Lalami · Thèses en ligne de l'Université Toulouse III (Université Toulouse III) · 2012
Combinatorial optimization problems are difficult problems whose solution by exact methods can be time consuming or not realistic. The use of heuristics permits one to obtain good quality solutions in a reasonable time. Heuristics are also very useful for the development of exact methods based on branch and bound techniques. The first part of this thesis concerns the Multiple Knapsack Problem (MKP). We propose here a heuristic called RCH which yields a good solution for the MKP problem. This approach is compared to the MTHM heuristic and CPLEX solver. The second part of this thesis concerns parallel implementation of an exact method for solving combinatorial optimization problems like knapsack problems on GPU architecture. The parallel implementation of the Branch and Bound method via CUDA for knapsack problems is proposed. Experimental results show a speedup of 51 for difficult problems using a Nvidia Tesla C2050 (448 cores). A CPU-GPU implementation of the simplex method for solving linear programming problems is also proposed. This implementation offers a speedup around 12.7 on a Tesla C2050 board. Finally, we propose a multi-GPU implementation of the simplex algorithm via CUDA. An efficiency of 96.5% is obtained when passing from one GPU to two GPUs.