The multi-terminal vertex separator problem: Polyhedral analysis and Branch-and-Cut
Cornaz, Denis; Magnouche, Youcef; Mahjoub, Ali Ridha; Martin, Sébastien (2015), The multi-terminal vertex separator problem: Polyhedral analysis and Branch-and-Cut, in Kacem, Imed, 45th International Conference on Computers & Industrial Engineering 2015 (CIE45), Curran Associates, Inc.. 10.1016/j.dam.2018.10.005
Type
Communication / ConférenceExternal document link
https://hal.univ-lorraine.fr/hal-01785327Date
2015Conference title
45th International Conference on Computers & Industrial Engineering 2015 (CIE45)Conference date
2015-08Conference city
MetzConference country
FranceBook title
45th International Conference on Computers & Industrial Engineering 2015 (CIE45)Book author
Kacem, ImedPublisher
Curran Associates, Inc.
ISBN
9781510817456
Publication identifier
Metadata
Show full item recordAuthor(s)
Cornaz, DenisLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Magnouche, Youcef
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mahjoub, Ali Ridha
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Martin, Sébastien

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
In this paper we consider a variant of the k-separator problem. Given a graph G=(V∪T,E) with V∪T the set of vertices, where T is a set of k terminals, the multi-terminal vertex separator problem consists in partitioning V∪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 size of S is minimum. In this paper, we first show that the problem is NP-hard. Then we give two integer programming formulations for the problem. For one of these formulations, we investigate the related polyhedron and discuss its polyhedral structure. We describe some valid inequalities and characterize when these inequalities define facets. We also derive separation algorithms for these inequalities. Using these results, we develop a Branch-and-Cut algorithm for the problem, along with an extensive computational study.Subjects / Keywords
Vertex separator problem; Integer programming; Polytope; Facet; Branch-and-Cut algorithm; Complexity; Separation algorithmRelated items
Showing items related by title and author.
-
Cornaz, Denis; Magnouche, Youcef; Mahjoub, Ali Ridha; Martin, Sébastien (2019) Article accepté pour publication ou publié
-
Lacroix, Mathieu; Mahjoub, Ali Ridha; Martin, Sébastien (2012) Communication / Conférence
-
Diarrassouba, Ibrahima; Mahjoub, Meriem; Mahjoub, Ali Ridha; Taktak, Raouia (2016) Article accepté pour publication ou publié
-
Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2014) Communication / Conférence
-
Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2019) Article accepté pour publication ou publié