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.