An exact algorithm for the capacitated shortest spanning arborescence |
| |
Authors: | Paolo Toth Daniele Vigo |
| |
Institution: | (1) DEIS, University of Bologna, Viale Risorgimento 2, I-40136 Bologna, Italy |
| |
Abstract: | We are given a complete and loop-free digraphG=(V, A), whereV={1,...,n} is the vertex set,A={(i, j) :i, j V} the arc set, andr V is a distinguishedroot vertex. For each arc (i, j) A, letc
ij
be the associatedcost, and for each vertexi, letq
i
0 be the associateddemand (withq
r
=0). Moreover, a nonnegativebranch capacity, Q, is defined.A Capacitated Shortest Spanning Arborescence rooted at r (CSSA
r
) is a minimum cost partial digraph such that: (i) each vertexj r has exactly one entering arc; (ii) for each vertexj r, a path fromr toj exists; (iii) for each branch leaving vertexr, the total demand of the vertices does not exceed the branch capacity,Q. A variant of theCSSA
r
problem (calledD-CSSA
r
) arises when the out-degree of the root vertex is constrained to be equal to a given valueD. These problems are strongly NP-hard, and find practical applications in routing and network design. We describe a new Lagrangian lower bound forCSSA
r
andD-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 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. |
| |
Keywords: | Capacitated shortest spanning arborescence Lagrangian relaxation branch-and-bound heuristic algorithms |
本文献已被 SpringerLink 等数据库收录! |
|