Linear Formulations and exact algorithms for Combinatorial Optimization
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.
Defence : 10/19/2018 - 14h - Site Jussieu 25-26-105
Jury members :
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
- PASS-LANNEAU Adèle : Ancrage de solutions en optimisation robuste.
- FALQ Anne-Elisabeth : Dominances en programmation linéaire : ordonnancement autour d’une date d’échéance commune.
- ROTTNER Cécile : Aspects combinatoires du "Unit Commitment Problem".
- QUESTEL Aurélien : Conception de réseaux en anneaux-étoiles et programmation mathématique.
- SEGURA Jean Mathieu : Localisation et affectation : application aux réseaux de contenus.