EUVIMEDOpdag EUVIMED
Open access · CC BY 4.0

An Extended Formulation With Valid Inequalities for the Capacitated Steiner Arborescence Problem

Francesco Contu, Massimo Di Francesco, Enrico Gorgone, Ishwar Murthy

Networks · 2026-09 · 88 (2) · 250-274

DOI: 10.1002/net.70053 ↗

At a glance

Journal article in Networks, published online on 2026-06-09. Written by Francesco Contu and 3 co-authors. 34 references. The full text is freely available (open access, CC BY 4.0).

AbstractBibliografiske oplysningerCiteRelated studies

Abstract (original language)

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.

Cite

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}
}
Start for free →