An Extended Formulation With Valid Inequalities for the Capacitated Steiner Arborescence Problem
Networks · 2026-09 · 88 (2) · 250-274
DOI: 10.1002/net.70053 ↗Kurz gefasst
Fachartikel in der Zeitschrift Networks, online erschienen am 09.06.2026. Verfasst von Francesco Contu und 3 weiteren Autor:innen. Die Arbeit nennt 34 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Given a directed graph, the Capacitated Steiner Arborescence Problem (CSAP) aims to determine the least‐cost connection from the root node to terminal nodes requiring a demand through Steiner nodes coming with a capacity, such that there is a unique path from the root to each terminal. This paper presents a new extended formulation of the CSAP, which extends the classical multicommodity flow formulation of CSAP by introducing the notion of cardinality of terminals served by arcs. We show that our extended formulation is stronger than the classical one. We present two classes of inequalities and separation heuristics exploiting the cardinality effect of the extended formulation. The first class is a generalization of cardinality induced Cover and (1, k )‐Configuration inequalities. The second class is called the p‐ Arc Cardinality matching inequalities and is based on matching the number of commodities flowing on active arcs across a cut‐set to its composite cardinality. The computational study clearly demonstrates the superiority of the extended formulation over the classical one. In particular, it consistently provides significantly tighter lower bounds at the root node. Moreover, for all hard instances, solving CSAP to optimality requires a number of branch‐and‐bound nodes that is several orders of magnitude larger under the classical formulation than under the extended one.
Zitieren
APA
Contu, F., Francesco, M. D., Gorgone, E., & Murthy, I. (2026). An Extended Formulation With Valid Inequalities for the Capacitated Steiner Arborescence Problem. Networks, 88(2), 250-274. https://doi.org/10.1002/net.70053
Vancouver
Contu F, Francesco MD, Gorgone E, Murthy I. An Extended Formulation With Valid Inequalities for the Capacitated Steiner Arborescence Problem. Networks. 2026;88(2):250-274. doi:10.1002/net.70053
BibTeX
@article{Contu2026,
author = {Contu, Francesco and Francesco, Massimo Di and Gorgone, Enrico and Murthy, Ishwar},
title = {An Extended Formulation With Valid Inequalities for the Capacitated Steiner Arborescence Problem},
journal = {Networks},
year = {2026},
volume = {88},
number = {2},
pages = {250--274},
doi = {10.1002/net.70053}
}
EUVIMED