Séminaire d'Optimisation Combinatoire

LAMSADE, Université Paris-Dauphine

Les anciens exposés de 2007

Vendredi 27 avril 2007 à 14h en salle A711
Sourour Elloumi, CNAM
Titre : Quelques questions d'optimisation discrète, linéaire et quadratique
Vendredi 2 novembre 2007 à 14h en salle A707
Onur Ozkök, Bilkent University, Ankara
Title: Two Level Survivable Network Design
Abstract: The two level survivable telecommunication network design consists of locating concentrators, assigning user nodes to concentrators and linking concentrators in a reliable backbone network. Various architectures could be used for either level. We study this problem when the backbone is 2-edge connected and when user nodes are linked to concentrators by a point-to-point access network. We formulate this problem as an integer linear program and analyze the polyhedral structure of the associated polytope. We describe valid inequalities and give sufficient conditions for these inequalities to be facet defining. Separation problems for facet defining inequalities are proposed. We also propose some reduction operations in order to speed up the separation procedures for these inequalities. Finally, we devise a branch-and-cut algorithm based on these results and present some computational results. Some future research directions are also discussed.
Vendredi 14 décembre 2007 à 13h en salle AR54
Ioan Todinca, LIFL, Université d'Orléans
Titre : Complétions d'intervalles minimales et largeur linéaire (pathwidth) des graphes
Résumé : Les graphes étant des objets complexes, on tente souvent de les "simplifier" si possible sans leur apporter beaucoup de modifications. Une technique courante consiste à rajouter des arêtes au graphe en entrée afin d'obtenir un graphe plus simple. Une complétion d'intervalles d'un graphe quelconque G est un graphe d'intervalles H, obtenu à partir de G en lui rajoutant des arêtes. On cherche classiquement à minimiser certains paramètres comme le nombre d'arêtes rajoutées ou la taille de la clique de cardinal maximum de H. Ces problèmes étant NP-difficiles, nous nous intéressons aux complétion d'intervalles minimales, où l'on demande simplement à ce que l'ensemble d'arêtes ajoutées soit minimal par inclusion. Je montrerai comment calculer une telle complétion et j'évoquerai des applications au calcul de la largeur linéaire pour des graphes particuliers.