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

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.