Invitation to attend the public PhD thesis defense of Raca Todosijevic at UVHC

Invitation to attend the public PhD thesis defense of Raca Todosijevic at UVHC (Université de Valenciennes et Hainaut-Cambrésis)

Theoretical and Practical Contributions on Scatter Search, Variable Neighborhood Search and Matheuristics for 0-1 Mixed Integer Programs

The defense will take place on  June 22, 3pm, IEMN, UVHC

The jury members are:

Rapporteurs :

M. Pierre HANSEN, Professeur des Universités, HEC Montréal, Canada.

M. Abraham PUNNEN, Professeur des Universités, Simon Fraser University, Canada.

Examinateurs :

M. Arnaud FREVILE               Professeur, LAMIH-UVHC, France

M. Fred GLOVER                    Professeur, Université de Colorado, USA

M. Nenad MLADENOVIC      Professeur, LAMIH-UVHC, France

M. Michel  VASQUEZ            Enseignant-Chercheur, HdR, Ecole des Mînes d’Alès, France

M. Saïd HANAFI                     Directeur de thèse, Professeur, LAMIH-UVHC, France

M. Bernard GENDRON           Directeur de thèse, Professeur, CIRRELT, Université de Montréal, Canada

 Abstract:

This thesis consists of results obtained studying Scatter Search, Variable Neighbourhood Search (VNS), and Matheuristics in both theoretical and practical context. Regarding theoretical results, one of the main contribution of this thesis is a convergent scatter search with directional rounding algorithm for 0-1 Mixed Integer Programs (MIP) with the proof of its finite convergence. Besides this, a convergent scatter search algorithm is accompanied by two variants of its implementation. Additionally, several scatter search based heuristics, stemming from a convergent scatter search algorithm have been proposed and tested on some instances of 0-1 MIP. The versions of the methods tested are ”first stage” implementations to establish the power of the methods in a simplified form. Our findings demonstrate the efficacy of these first stage methods, which makes them attractive for use in situations where very high quality solutions are sought with an efficient investment of computational effort.

This thesis also includes a several new variants of Variable Neighborhood Search metaheuristic such as a two-level variable neighborhood search, a nested variable neighborhood search, a cyclic variable neighborhood descent and a variable neighborhood diving.  Additionally, several efficient implementation of those variable neighborhood search algorithms have been successfully applied for solving NP-Hard problems appearing in transportation, logistics, power generation, scheduling and clustering. On all tested problems, the proposed VNS heuristics turned out to be a new state-of-the art heuristics.

The last contribution of this thesis consists of proposing several matheuristics for solving Fixed-Charge Multicommodity Network Design (MCND). The performances of these matheuristics have been disclosed on benchmark instances for MCND. The obtained results demonstrate the competitiveness of the proposed matheuristics with other existing approaches in the literature.

 Keywords: Optimization - Scatter Search - Variable Neighborhood Search - Heuristic - Metaheuristic – Matheuristic – Directional rounding – Convergence; 0-1 MIP- Routing – TSP-VRP-Location- Clustering-Scheduling-Maintenance-Unit commitment- Network Design