Minimum-weight rooted not-necessarily-spanning arborescence problem

In this paper, we propose the problem of identifying a minimum-weight rooted not-necessarily-spanning arborescence (MRA) in a directed rooted acyclic graph with weights on arcs. We show this problem to be NP-hard and formulate it as a zero—one integer program. We develop a heuristic H to construct a rooted arborescence (RA) in a given graph G, giving an upper bound. We also formulate a Lagrangian problem, LMRA, by relaxing one set of constraints of the zero—one integer program. For a given set of Lagrange multipliers, LMRA can be easily solved to obtain a lower bound. Then, we propose a Lagrangian heuristic, L, that generates both a lower bound and an upper bound in each iteration. The above heuristics were tested with 50 test problems. We also compared the performance of L with a general-purpose optimization package, CPLEX, using 12 test problems. The results show that L was able to identify an optimal solution in almost all cases. CPLEX found an optimal solution in all cases, but was not able to verify optimality in some instances. © 2002 Wiley Periodicals, Inc.