Soutenance de thèse de Luc Libralesso (ROSP) le 24 juillet 2020 à 14h00 en amphi Gosse - Site Viallet - Grenoble INP

Les membres du jury :
 

• Monsieur Christian ARTIGUES - Directeur de Recherche, CNRS, LAAS, Rapporteur
• Monsieur Louis ESPERET - Chargé de Recherche, CNRS, G-SCOP, Directeur de thèse
• Monsieur Jin-Kao HAO - Professeur, Université d’Angers, Rapporteur
• Monsieur Thibault HONEGGER - Chief Scientific Officer, NETRI, Co-encadrant de thèse
• Monsieur Vincent JOST - Chargé de recherche CNRS, G-SCOP, Co-encadrant de thèse
• Madame Christine SOLNON - Professeur, INSA de Lyon, Examinateur
• Monsieur Vincent T’KINDT - Professeur, Université de Tours, Examinateur

Résumé :

Les recherches arborescentes sont utilisées dans un grand nombre d'applications (MIP, CP, SAT, meta-heuristiques avec Ant Colony Optimization et GRASP) et également dans des communautés IA/planning. Toutes ces techniques présentent des bases communes et de nombreuses techniques peuvent être transférées d'une communauté à une autre. Les résultats préliminaires indiquent que ces techniques ont toute leur place dans la boite a outils des méthodes les plus performantes en recherche opérationnelle. Dans ces travaux, nous dressons un état de l'art et une classification de différentes techniques de recherche arborescente que l'on retrouve dans les meta-heuristiques, dans les méthodes exactes et en IA/planning. Nous développons un framework générique qui permet l'élaboration rapide d'algorithmes de recherche arborescente. Enfin, nous utilisons ces techniques pour proposer des méthodes compétitives avec les meta-heuristiques généralement utilisées en recherche opérationnelle. Nous présentons de nouvelles méthodes de recherche arborescente pour plusieurs problèmes d'optimisation combinatoire ainsi que de nouvelles meilleures solutions connues.

Messages principaux :
 

• Les recherches arborescentes anytime peuvent être compétitifs comparé aux meta-heuristiques classiques sur des instances de grande taille grâce aux recherches arborescentes anytime.
• La combinaison de composants algorithmiques habituellement utilisés par différentes communautés (IA, CP, meta-heuristiques, branch-and-bound) ainsi que l'étude des contributions de ces composants permet de produire des algorithmes nouveaux, compétitifs, et parfois plus simples que les méthodes état de l'art issues de chacune de ces communautés.

Abstract :

Tree search algorithms are used in a large variety of applications (MIP, CP, SAT, metaheuristics with Ant Colony Optimization and GRASP) and also in AI/planning communities. All of these techniques present similar components and many of those components can be transferred from one community to another. Preliminary results indicate that anytime tree search (search techniques from AI/planning) can be part of the operations research toolbox as they are simple and competitive compared to commonly used metaheuristics in operations research.
In this work, we detail a state of the art and a classification of the different tree search techniques that one can find in metaheuristics, exact methods, and AI/planning. Then, we present a generic framework that allows the rapid prototyping of tree search algorithms. Finally, we use this framework to develop anytime tree search algorithms that are competitive with the commonly-used metaheuristics in operations research. We report new tree search applications for some combinatorial optimization problems and new best-known solutions.

Main messages :
 

• anytime tree search algorithms can be competitive with classical meta-heuristics on large scale discrete optimization instances by using anytime tree search strategies.
• The combination of algorithmic components from different communities (AI, CP, meta-heuristics, branch-and-bounds) combined with a study on the contribution of each component leads to new algorithms that are competitive, and sometimes, even simpler than the state-of-the-art methods from each of these communities.