QUESTEL Aurélien

Docteur
Équipe : RO
Date de départ : 31/12/2013
Direction de recherche : Philippe CHRÉTIENNE
Co-encadrement : FOUILHOUX Pierre

Conception de réseaux en anneaux-étoiles et programmation mathématique

Nous considérons ici le problème de couverture de graphe par des anneaux-étoiles. Nous montrons que ce problème modélise le problème de conception de réseaux de télécommunications SDH. Nous discutons de la caractérisation d'une solution à ce problème et proposons plusieurs formulations linéaires en nombres entiers. Nous menons par la suite une étude polyédrale sur un dominant de la formulation naturelle et développons un algorithme de Branch-and-Cut pour résoudre des instances générées aléatoirement. Nous proposons également une formulation à nombre exponentiel de variables résolue par une méthode de génération de colonnes.
Nous discutons du problème auxiliaire et montrons que sa résolution par un algorithme de Branch-and-Cut permet d'introduire des contraintes issues du polytope du Set partionning dans le problème maître.
Soutenance : 30/05/2013 - 14h - Site Jussieu, amphi 45B
Membres du jury :
Andrea LODI, University of Bologna - DEIS [Rapporteur]
Frédéric SEMET, Ecole Centrale de Lille - LAGIS [Rapporteur]
Philippe CHRÉTIENNE, UPMC - LIP6 (directeur)
Pierre FOUILHOUX, UPMC - LIP6 (encadrant)
A. Ridha MAHJOUB, Université Paris Dauphine - LAMSADE (président)
Michel MINOUX, UPMC - LIP6
Eric PINSON, IMA - LISA

Publications 2011-2014

 Mentions légales
Carte du site |