Skip to Main content Skip to Navigation
New interface

Contribution à la résolution de problèmes d'optimisation combinatoire : méthodes séquentielles et parallèles

Mohamed Esseghir Lalami 1 
1 LAAS-CDA - Équipe Calcul Distribué et Asynchronisme
LAAS - Laboratoire d'analyse et d'architecture des systèmes
Abstract : 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.
Document type :
Complete list of metadata

Cited literature [2 references]  Display  Hide  Download
Contributor : Emilie Marchand Connect in order to contact the contributor
Submitted on : Monday, November 5, 2012 - 2:37:45 PM
Last modification on : Tuesday, October 25, 2022 - 11:58:11 AM
Long-term archiving on: : Wednesday, February 6, 2013 - 3:55:03 AM


  • HAL Id : tel-00748546, version 1


Mohamed Esseghir Lalami. Contribution à la résolution de problèmes d'optimisation combinatoire : méthodes séquentielles et parallèles. Automatique. Université Paul Sabatier - Toulouse III, 2012. Français. ⟨NNT : ⟩. ⟨tel-00748546⟩



Record views


Files downloads