An exact algorithm for the capacitated shortest spanning arborescence

We are given a complete and loop-free digraph G = (V, A), where V = {l,...,n} is the vertex set, A = {(i,j) : i,j is an element of V} the are set, and r is an element of V is a distinguished root vertex. For each are (i,j) is an element of A, let c(ij) be the associated cost, and for each vertex i, let q(i) greater than or equal to 0 be the associated demand (with q(r) = 0). Moreover, a nonnegative branch capacity, Q, is defined. A Capacitated Shortest Spanning Arborescence rooted at r (CSSA(r)) is a minimum cost partial digraph such that: (i) each vertex j not equal r has exactly one entering arc; (ii) for each vertex j not equal 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 CSSA(r) problem (called D-CSSA(r)) 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. We describe a new Lagrangian lower bound for CSSA(r) and D-CSSA(r) problems, strengthened in a cutting plane fashion by iteratively adding violated constraints to the Lagrangian problem. We 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 performace 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.