FOUILHOUX Pierre

Habilitation à Diriger des Recherches
Équipe : RO
Date de départ : 19/10/2018
https://lip6.fr/Pierre.Fouilhoux

Linear Formulations and exact algorithms for Combinatorial Optimization

Ce document présente plusieurs contributions autour des structures polyédrales et d'algorithmes permettant d'obtenir des solutions optimales de problèmes d'optimisation combinatoire.
Des propriétés polyédrales sont étudiées pour plusieurs problèmes comme ceux du sous-graphe biparti induit, de la conception de réseaux fiables de télécommunications hiérarchiques ou d'ordonnancement juste à temps. Des techniques génériques de construction de facettes ou de caractérisation de polytopes sont également présentées. Des algorithmes de coupes et branchements sont issus de ces études pour résoudre des instances de problèmes en conception de circuits électroniques, en génomique ou en télécommunications.
Trois aspects sont abordés concernant la résolution algorithmique de la programmation linéaire en nombres entiers. Des algorithmes mêlant algorithmes de coupes et de génération de colonnes sont prouvés efficaces pour des problèmes de coloration de graphes et de planification. Deux techniques permettant de limiter l'exploration de solutions symétriques dans les arborescence sont déduites de l'orbitope des permutations de colonnes. Enfin, un ensemble de procédés polyédraux permettent de linéariser des problèmes divers à objectifs non-linéaires en allocation de ressources ou en construction d'horaires de transport public.
Une troisième partie rassemble trois problèmes de recherche opérationnelle dont l'étude a mené à des résultats théoriques et pratiques. Il est montré que permuter des pièces l'une après l'autre dans un graphe correspond au renouvellement du combustible nucléaire. Le problème de planification des unités de production électriques est vu comme un problème d'ordonnancement avec des contraintes de durée sur les unités. Les problèmes de réparation et de prévision de calendrier d'un projet sont abordés dans l'objectif de maintenir le plus grand nombre de dates malgré des incertitudes sur les durées des tâches à réaliser. Pour chacun de ces problèmes, une étude de complexité et plusieurs approches algorithmiques sont présentés afin de résoudre exactement des instances de grande taille.

Soutenance : 19/10/2018

Membres du jury :

Luis Eduardo Neves GOUVEIA, Lisbon University, Portugal [Rapporteur]
Jon LEE, University of Michigan, United-States [Rapporteur]
Giovanni RINALDI, IASI, Italy [Rapporteur]
Mourad BAIOU, LIMOS-CNRS, Clermont-Ferrand, France
Philippe CHRÉTIENNE, Sorbonne University, France
Martine LABBÉ, Free University of Brussels, Belgium
A. Ridha MAHJOUB, Paris Dauphine University, France

Date de départ : 19/10/2018

5 Docteurs 2011 - 2021

Mentions légales
Carte du site