LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » Jobs

 Thesis : Polyèdres de couvertures de graphes et génération de colonnes

PhD school thesis
Plusieurs problèmes bien différents d'optimisation combinatoire issus de la Recherche Opérationnelle ont une même structure ``Set Covering'' (tournées de véhicules, coloration de graphes...). Elle mène à formulations linéaires en nombres entiers possédant un nombre exponentiel de variables, et qui peuvent être résolues par des méthodes de génération de colonnes. L'approche proposée ici est d'étudier les polyèdres associées à ces formulations dans deux buts: l'un théorique pour déduire des caractérisations de polyèdres dans des cas polynomiaux; l'autre pratique par des inégalités renforçant ces formulations pour des méthodes Branch&Price&Cut. Bien que la technique de Branch&Price est fortement utilisée en industrie, les méthodes de Branch&Cut&Price ont été peu étudiées compte-tenu de leur difficulté de mise en oeuvre: l'approche polyédrale, qui a fait ses preuves dans d'autres cadres, peut palier à ces difficultés.

Mots clefs : Optimisation combinatoire, Programmation mathématique, Graphes, Applications en recherche opérationnelle, Formulations "Set Covering", Approches polyédrales

Ce projet de recherche doctoral fait l’objet d’une demande de financement auprès de « Ecole Doctorale d‘Informatique, Télécommunication et d‘Electronique (EDITE) », le candidat retenu par son porteur devra donc participer au concours correspondant (prévoir un dossier et une audition) en vue d’obtenir le financement effectif.

More details here

Contact :Pierre Fouilhoux

 Mentions légales
Site map |