Show simple item record

hal.structure.identifierSchool of Computer Science and Engineering [Chengdu] [UESTC]
dc.contributor.authorMa, Mengfan
ORCID: 0000-0002-4478-3479
hal.structure.identifierDepartment of Computer Science & Engineering [Riverside] [CSE]
dc.contributor.authorMen, Ziyang
ORCID: 0000-0001-7290-690X
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorRossi, André
HAL ID: 1694
hal.structure.identifierSchool of Computer Science and Engineering [Chengdu] [UESTC]
dc.contributor.authorZhou, Yi
hal.structure.identifierSchool of Computer Science and Engineering [Chengdu] [UESTC]
dc.contributor.authorXiao, Mingyu
dc.date.accessioned2023-08-22T14:49:02Z
dc.date.available2023-08-22T14:49:02Z
dc.date.issued2023
dc.identifier.issn0305-0548
dc.identifier.urihttps://basepub.dauphine.psl.eu/handle/123456789/24867
dc.language.isoenen
dc.subjectPartitioned Steiner tree problemen
dc.subjectInteger linear programen
dc.subjectVertex-separatoren
dc.subjectBranch-and-cuten
dc.subjectLocal branchingen
dc.subject.ddc003en
dc.titleA vertex-separator-based integer linear programming formulation for the partitioned Steiner tree problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenGiven an undirected graph G with a cost function on vertices, a collection of subgraphs of G such that in each subgraph, there are some distinguished vertices called terminals, the Partitioned Steiner Tree Problem (PSTP) asks for a minimum cost vertex set such that, in each of the given subgraph G_i, the graph induced by the vertex set spans the terminal set in G_i. The PSTP generalizes the well-known Steiner tree problem and has important applications in computational sustainability, network design, and social network analysis. However, for solving the PSTP, conventional integer programming approaches based on single-commodity flow, multi-commodity flow and subtour elimination integer linear programs, suffer from low computational efficiency due to a substantial number of variables. In this paper, we propose a compact vertex-separator-based integer linear programming formulation with much fewer variables. Enhancing inequalities are also studied for tightening the formulation. We further investigate a branch-and-cut algorithm, a local-branching heuristic algorithm, and a hybrid algorithm combining them. In experiments where both public real-world and synthetic graphs are used, our hybrid algorithm outperforms all conventional approaches, especially for large graphs with more than ten thousand vertices. Further tests also validate the effectiveness of the proposed formulation and enhancing inequalities.en
dc.relation.isversionofjnlnameComputers and Operations Research
dc.relation.isversionofjnlvol153en
dc.relation.isversionofjnldate2023-05
dc.relation.isversionofjnlpages106151en
dc.relation.isversionofdoi10.1016/j.cor.2023.106151en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenon
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2023-08-22T14:30:35Z
hal.export.arxivnonen
hal.export.pmcnonen
hal.hide.repecnonen
hal.hide.oainonen
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


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