Séminaire d'Optimisation Combinatoire

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

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.