Auteur : Luc LIBRALESSO
Directeur de thèse : Louis ESPERET
Co encadrant : Thibault HONEGGER
Co encadrant : Vincent JOST
Date : 24 juillet 2020
Les recherches arborescentes sont utilisées dans un grand nombre d'applications (MIP, CP, SAT, meta-heuristiques avec l'optimisation par colonies de fourmi ou GRASP) et également dans les communautés de planification en intelligence artificielle. 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-à-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 planification. 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.
Directeur de thèse : Louis ESPERET
Co encadrant : Thibault HONEGGER
Co encadrant : Vincent JOST
Date : 24 juillet 2020
Recherches arborescentes anytime pour l’optimisation combinatoire
Les recherches arborescentes sont utilisées dans un grand nombre d'applications (MIP, CP, SAT, meta-heuristiques avec l'optimisation par colonies de fourmi ou GRASP) et également dans les communautés de planification en intelligence artificielle. 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-à-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 planification. 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.