Minimum-weight rooted not-necessarily-spanning arborescence problem

✍ Scribed by V. Venkata Rao; R. Sridharan

• Publisher: John Wiley and Sons
• Year: 2002
• Tongue: English
• Weight: 687 KB
• Volume: 39
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.10015

✦ Synopsis

Abstract

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.