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

Publications 2011-2014

• 2014
  • P. Fouilhoux, A. Questel : “A Branch-and-Cut for the non-disjoint m-Ring-Star problem”, RAIRO - Operations Research, vol. 48 (2), pp. 167-188, (EDP Sciences) (2014)
  • P. Fouilhoux, A. Questel : “Branch-and-Cut-and-Price using Stable Set polytope inequalities for the Capacitated- Ring-Star Problem”, International Symposium on Combinatorial Optimization (ISCO 2014), Lisbon, Portugal (2014)
• 2013
  • A. Questel : “Conception de réseaux en anneaux-étoiles et programmation mathématique”, soutenance de thèse, soutenance 30/05/2013, direction de recherche Chrétienne, Philippe, co-encadrement : Fouilhoux, Pierre (2013)
  • P. Fouilhoux, A. Questel : “Générer des colonnes par Branch-and-Cut: application au problème de couverture d’un graphe par des anneaux-étoiles”, Journées Polyèdres et Optimisation Combinatoire, JPOC8, Clermont-Ferrand, France (2013)
  • P. Fouilhoux, A. Questel, S. Loyal : “Générer des colonnes par un algorithme de branch‐and‐cut : application au problème de couverture par des anneaux‐étoiles multi‐dépôts”, 14^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2013), Troyes, France (2013)
• 2012
  • P. Fouilhoux, A. Questel : “Approche polyédrale pour le problème de couverture par des anneaux-étoile non-disjoints”, 13^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2012), Angers, France (2012)
  • P. Fouilhoux, A. Questel : “The Non-Disjoint m-Ring-Star Problem : polyhedral results and SDH/SONET network design”, International Symposium on Combinatorial Optimization (ISCO 2012), vol. 7422, Lecture Notes in Computer Science, Athènes, Greece, pp. 93-104, (Springer) (2012)
• 2011
  • P. Fouilhoux, A. Questel : “Non-disjoint Steiner m-Q-Ring-Star Problem : application à la conception de réseau SDH”, Journées Polyèdres et Optimisation Combinatoire, Valenciennes, France (2011)
  • P. Fouilhoux, A. Questel : “The Non-Disjoint m-Ring-Star Problem : application to SDH network design”, International Network Optimization Conference, Hamburg, Germany (2011)
  • P. Fouilhoux, A. Questel : “Non-Disjoint Steiner M-Q-Ring-Star Problem : Application À La Conception De Réseau Sdh”, 12^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2011), Saint-Étienne, France (2011)