Premium
Minimum‐weight rooted not‐necessarily‐spanning arborescence problem
Author(s) -
Rao V. Venkata,
Sridharan R.
Publication year - 2002
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10015
Subject(s) - heuristics , mathematics , upper and lower bounds , lagrange multiplier , mathematical optimization , heuristic , combinatorics , graph , integer programming , integer (computer science) , set (abstract data type) , branch and bound , computer science , mathematical analysis , programming language
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.