Séminaire du LIF
Jeudi 28 avril à 14h - Luminy, Amphi 12
Viet Hung NGuyen
LIP6 - Univ. Pierre et Marie Curie, Paris 6
Sur le polyèdre associé au problème Anneau-étoile
Le problème Anneau-étoile (uk: Ring Star Problem, RSP) a été introduit dans [1]. Il s'agit de trouver un cycle simple traversant un sous-ensemble de sommets d'un graphe de manière à ce que la somme du coût liant à la longueur du cycle et le coût d'affectation du reste des sommets aux plus proches sommets dans le cycle, soit minimum. Ce problème a des applications dans les réseaux de télécommunications et quelques-uns d'entre eux ont été décrits dans [1].
RSP est NP-difficile car le cas spécial dans lequel le côut d'affectation est extrêmement grand par rapport aux côut d'anneau est le problème du voyageur de commerce.
Dans [1], les auteurs ont présenté une description polyhédrale partielle du RSP, de même qu'un algorithme de Branch-and-Cut basé sur la description donnée et ont pu résoudre des instances ayant jusqu'à 300 sommets. Cette description est très inspirée d'une caractérisation partielle du polyèdre des cycles de P. Bauer.
Dans cet exposé, nous donnons une formulation mathématique basée sur une caractérisation des st-chemins et décrivons de nouvelles facettes ; nous présentons enfin un algorithme de Branch-and-cut pour RSP implémenté avec COIN/BCP.
[1] M. Labbe, G. Laporte, I.R. Martin and J.J.S. Gonzalez. The Ring Star Problem: Polyhedral Analysis and Exact Algorithm. Networks, 43(3):177-189, 2004.
[2] J.F. Maurras and V.H. Nguyen. On the linear description of 3-cycle polytope. EJOR, 137:310-325, 2002.
[3] P. Bauer. The circuit polytope: facets. Math Oper Res, 22:110-145, 1997.