Supervision : Philippe CHRÉTIENNE

Co-supervision : FOUILHOUX Pierre

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

In this document, we adress the problem of covering a graph with ring-stars. We show that designing a SDH networks reduces to solving the ring-star covering problem. We discuss the encoding of a solution and present three integer programming formulations. We study from a polyhedral point of view the dominant of the polytope associated to the natural formulation and develop a Branch-and-Cut algorithm based on these results. We also propose a set partitionning formulation containing an exponential number of variables that we solve by a column generation technique. Since the classical algorithmic approach would not lead to an efficient pricing procedure, we present a method that allows to handle set partitionning inequalities using a Branch-and-Cut algorithm to solve the auxiliary problem. The resulting Branch-and-Cut-and-Price algorithm is tested on randomly generated instances.

2011-2014 Publications

• 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”, thesis, phd defence 05/30/2013, supervision Chrétienne, Philippe, co-supervision : 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)