LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » أحـداث السـاعـة » مسجلون في الدكتوراه

QUESTEL Aurélien

وحـدة : RO
تاريـخ المـغادرة : 31/12/2013
رئاسـة البـحث : Philippe CHRÉTIENNE
تأطـير مـشـترك : 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.
مناقـشـة مـذكـرة : 30/05/2013 - 14h - Site Jussieu, amphi 45B
أعـضاء لجنة المناقـشة :
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)

إصدارات 2011-2014

 Mentions légales
| خـريـطـة المـوقـع