Soutenance de Mirsad Buljubasic

Soutenance de THÈSE


Présentée par


Spécialité: I2S informatique


Efficient local search for several combinatorial optimization problems


Le vendredi 20 novembre 2015


Salle de conférence, site de Nîmes école des mines d’Alès



Devant le jury composé de :

Michel Vasquez      Ecole des mines d'Alès Directeur de thèse
Haris Gavranovic Université de Sarajevo Co-Directeur de thèse
Mutsunori Yagiura Université de Nagoya   Rapporteur
Jin Kao Hao Université d’Angers Rapporteur
Miklos Molnar LIRMM Examinateur
Said Hanafi Université de Valenciennes Examinateur

Résumé: This Ph.D. thesis concerns algorithms for Combinatorial Optimization Problems. In Combinatorial Optimization
Problems the set of feasible solutions is discrete or can be reduced to a discrete one, and the goal is to find the best
possible solution. Specifically, in this research we consider three different problems in the field of Combinatorial
Optimization including One-dimensional Bin Packing (and two similar problems), Machine Reassignment Problem
and Rolling Stock Problem. The first one is a classical and well known optimization problem, while the other two
are real world and very large scale problems arising in industry and have been recently proposed by Google and
French Railways (SNCF) respectively. For each problem we propose a local search based heuristic algorithm and
we compare our results with the best known results in the literature. Additionally, as an introduction to local search
methods, two metaheuristic approaches, GRASP and Tabu Search are explained through a computational study on
Set Covering Problem.

Mots clés:

Local Search, Combinatorial Optimization