HDR "Habilitation à Diriger des Recherches"
Pierre Fouilhoux
Soutenance
Vendredi 19 octobre 2018
A partir de 14h
Au laboratoire
LIP6
de Sorbonne Université (ex-UPMC-Paris VI)
Campus Pierre et Marie Curie
4 place Jussieu 75005 Paris
Dans la salle
Rotonde 26 - 1er étage - Couloir 25-26 - Salle 105
Manuscrit
Titre: "Linear Formulations and exact algorithms for Combinatorial Optimization"
Document en PDF: Document HDR
Soutenance en PDF: HDR
Jury
| Luis Eduardo Neves GOUVEIA | (reviewer) |
Lisbon University, Portugal |
| Jon LEE | (reviewer) |
University of Michigan, United-States |
| Giovanni RINALDI | (reviewer) |
IASI-CNR, Italy |
| Mourad BAIOU |
| LIMOS-CNRS, Clermont-Ferrand, France |
| Philippe CHRÉTIENNE |
| Sorbonne University, France |
| Martine LABBÉ |
| Free University of Brussels, Belgium |
| A. Ridha MAHJOUB | (advisor) |
Paris Dauphine University, France |
Résumé
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.
Abstract
This manuscript proposes some contributions dealing with polyhedral structures and algorithms providing optimal solutions of some combinatorial optimization problems.
Some polyhedral properties are studied for several problems like the bipartite induced subgraph, the survivable hierarchical telecommunication network design or the just-in-time scheduling problems. Some generic techniques leading to construct facets or characterizing some polytopes are also introduced. Some Branch-and-Cut algorithms are devised from these studies in order to solve instances of problems dealing with VLSI design, genomics or telecommunications.
Three aspects are presented about algorithmic solving of integer linear programs. Some algorithms mixing cut and column generation are shown to be efficient for graph coloring and planning problems. Two techniques leading to reduce the exploration of symmetric solutions within arborescences are deduced from the orbitope of column permutations. Finally, several polyhedral methods aim to linearize distinct problems having non-linear objectives: such problems can be found in resource assignment or public transportation timetabling.
A last part gathers three operational research problems whose studies have lead to theoretical and practical results. It is shown that permuting pieces one after the other on a graph is equivalent to the nuclear power plant fuel renewal. The unit commitment problem for electricity production is presented as a scheduling problem with duration constraints. Repairing or planning a project schedule is studied in order to maintain a maximum number of dates when some aleas occur over task durations. For each of these problems, a complexity analysis together with several algorithmic approaches lead to exactly solve large size instances.
