Show simple item record

dc.contributor.authorCornaz, Denis
dc.contributor.authorMagnouche, Youcef
dc.contributor.authorMahjoub, Ali Ridha
dc.contributor.authorMartin, Sébastien
dc.date.accessioned2020-09-04T13:58:15Z
dc.date.available2020-09-04T13:58:15Z
dc.date.issued2015
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20971
dc.language.isoenen
dc.subjectVertex separator problemen
dc.subjectInteger programmingen
dc.subjectPolytopeen
dc.subjectFaceten
dc.subjectBranch-and-Cut algorithmen
dc.subjectComplexityen
dc.subjectSeparation algorithmen
dc.subject.ddc519en
dc.titleThe multi-terminal vertex separator problem: Polyhedral analysis and Branch-and-Cuten
dc.typeCommunication / Conférence
dc.description.abstractenIn 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.en
dc.relation.ispartoftitle45th International Conference on Computers & Industrial Engineering 2015 (CIE45)en
dc.relation.ispartofeditorKacem, Imed
dc.relation.ispartofpublnameCurran Associates, Inc.en
dc.identifier.urlsitehttps://hal.univ-lorraine.fr/hal-01785327en
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
dc.relation.ispartofisbn9781510817456en
dc.relation.conftitle45th International Conference on Computers & Industrial Engineering 2015 (CIE45)en
dc.relation.confdate2015-08
dc.relation.confcityMetzen
dc.relation.confcountryFranceen
dc.relation.forthcomingnonen
dc.identifier.doi10.1016/j.dam.2018.10.005en
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2020-09-04T13:49:25Z
hal.person.labIds989
hal.person.labIds989
hal.person.labIds989
hal.person.labIds989


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record