The authors are given a complete and loop-free digraph G=(V,a), where V={1,...,n} is the vertex set, A={(i,j):i,j∈V} the arc set, and r∈V is a distinguished root vertex. For each arc (i,j)∈A, let cij be the associated cost, and for each vertex i, let qi∈0 be the associated demand (with qr=0). Moreover, a nonnegative branch capacity, Q, is defined. A Capacitated Shortest Spanning Arborescence rooted ar r (CSSAr) is a minimum cost partial digraph such that: (i) each vertex jℝr has exactly one entering arc; (ii) for each vertex jℝr, a path from r to j exists; (iii) for each branch leaving vertex r, the total demand of the vertices does not exceed the branch capacity, Q. A variant of the CSSAr problem (called D-CSSAr) arises when the out-degree of the root vertex is constrained to be equal to a given value D. These problems are strongly NP-hard, and find practical applications in routing and network design. The authors describe a new Lagrangian lower bound for CSSAr and D-CSSAr problems, strengthened in a cutting plane fashion by iteratively adding violated constraints to the Lagrangian problem. They also present a new lower bound based on projection leading to the solution of min-cost flow problems. The two lower bounds are then combined so as to obtain an overall additive lower bounding procedure. The additive procedure is then imbedded in a branch-and-bound algorithm whose performance is enhanced by means of reduction procedures, dominance criteria, feasibility checks and upper bounding. Computational tests on asymmetric and symmetric instances from the literature, involving up to 200 vertices, are given, showing the effectiveness of the proposed approach.
