QUESTEL Aurélien
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
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
Pierre FOUILHOUX, UPMC - LIP6
A. Ridha MAHJOUB, Université Paris Dauphine - LAMSADE
Michel MINOUX, UPMC - LIP6
Eric PINSON, IMA - LISA