• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

The multi-terminal vertex separator problem : Complexity, Polyhedra and Algorithms

Le problème du séparateur de poids minimum : Complexité, Polyèdres et Algorithmes

Magnouche, Youcef (2017), The multi-terminal vertex separator problem : Complexity, Polyhedra and Algorithms, doctoral thesis prepared under the supervision of Mahjoub, Ali Ridha, Université Paris Dauphine

View/Open
2017PSLED020.pdf (2.786Mb)
Type
Thèse
Date
2017-06-26
Metadata
Show full item record
Author(s)
Magnouche, Youcef
Under the direction of
Mahjoub, Ali Ridha
Abstract (FR)
Étant donné un graphe G = (V U T, E), tel que V U T représente l'ensemble des sommets où T est un ensemble de terminaux, et une fonction poids w associée aux sommets non terminaux, le problème du séparateur de poids minimum consiste à partitionner V U T en k + 1 sous-ensembles {S, V1,..., Vk} tel qu'il n'y a aucune arête entre deux sous-ensembles différents Vi et Vj, chaque Vi contient exactement un terminal et le poids de S est minimum. Dans cette thèse, nous étudions le problème d'un point de vue polyèdral. Nous donnons deux formulations en nombres entiers pour le problème, et pour une de ces formulations, nous étudions le polyèdre associé. Nous présentons plusieurs inégalités valides, et décrivons des conditions de facette. En utilisant ces résultats, nous développons un algorithme de coupes et branchement pour le problème. Nous étudions également le polytope des séparateurs dans les graphes décomposables par sommets d'articulation. Si G est un graphe qui se décompose en G1 et G2, alors nous montrons que le polytope des séparateurs dans G peut être décrit à partir de deux systèmes linéaires liés à G1 et G2. Ceci donne lieu à une technique permettant de caractériser le polytope des séparateurs dans les graphes qui sont récursivement décomposables. Ensuite, nous étudions des formulations étendues pour le problème et proposons des algorithmes de génération de colonnes et branchement ainsi que des algorithmes de génération de colonnes, de coupes et branchement. Pour chaque formulation, nous présentons un algorithme de génération de colonnes, une procedure pour le calcul de la borne duale ainsi qu'une règle de branchement. De plus, nous présentons quatre variantes du problème du séparateur. Nous montrons que celles-ci sont NP-difficiles, et pour chacune d'elles nous donnons une formulation en nombres entiers et présentons certaines classes d'inégalités valides.
Abstract (EN)
Given a graph G = (V U T, E) with V U T the set of vertices, where T is a set of terminals, and a weight function w, associated with the nonterminal nodes, the multi-terminal vertex separator problem consists in partitioning V U T into k + 1 subsets {S, V1,..., Vk} such that there is no edge between two different subsets Vi and Vj, each Vi contains exactly one terminal and the weight of S is minimum. In this thesis, we consider the problem from a polyhedral point of view. We give two integer programming formulations for the problem, for one of them, we investigate the related polyhedron. We describe some valid inequalities and characterize when these inequalities define facets. Using these results, we develop a Branch-and-Cut algorithm for the problem. We also study the multi-terminal vertex separator polytope in the graphs decomposable by one node cutsets. If G is a graph that decomposes into G1 and G2, we show that the multi-terminal vertex separator polytope in G can be described from two linear systems related to G1 and G2. This gives rise to a technique for characterizing the multi-terminal vertex separator polytope in the graphs that are recursively decomposable. Moreover, we propose three extended formulations for the problem and derive Branch-and-Price and Branch-and-Cut-and-Price algorithms. For each formulation we present a column generation scheme, the way to compute the dual bound, and the branching scheme. Finally, we discuss four variants of the multi-terminal vertex separator problem. We show that all these variants are NP-hard and for each one we give an integer programming formulation and present some class of valid inequalities.
Subjects / Keywords
Optimisation combinatoire; Polytope; Facette; Coupes et branchements; Génération de colonnes; Composition de polyèdres; Combinatorial optimization; Polytope; Facet; Branch-And-Cut algorithm; Branch-And-Price algorithm; Composition of polyhedra

Related items

Showing items related by title and author.

  • Thumbnail
    The multi-terminal vertex separator problem: Polyhedral analysis and Branch-and-Cut 
    Cornaz, Denis; Magnouche, Youcef; Mahjoub, Ali Ridha; Martin, Sébastien (2019) Article accepté pour publication ou publié
  • Thumbnail
    The multi-terminal vertex separator problem: Polyhedral analysis and Branch-and-Cut 
    Cornaz, Denis; Magnouche, Youcef; Mahjoub, Ali Ridha; Martin, Sébastien (2015) Communication / Conférence
  • Thumbnail
    Approches de résolution exacte et approchée en optimisation combinatoire multi-objectif, application au problème de l'arbre couvrant de poids minimal 
    Lacour, Renaud (2014-07) Thèse
  • Thumbnail
    The Minimum Rooted-Cycle Cover Problem 
    Cornaz, Denis; Magnouche, Youcef (2018) Communication / Conférence
  • Thumbnail
    Gestion de la sécurité dans les systèmes de télécommunications : modèles, polyèdre et algorithmes 
    Naghmouchi, Mohamed yassine (2019-06-17) Thèse
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo