DIRECTED STEINER TREE PROBLEM ON A GRAPH: MODELS, RELAXATIONS AND ALGORITHMS.

The Steiner Problem in graphs is the problem of finding a set of edges (arcs) with minimum total weight which connects a given set of nodes in an edge-weighted graph (directed or undirected). This paper develops models for the directed Steiner tree problem on graphs. New and old models are examined in terms of their amenability to solution schemes based on Lagrangean relaxation. As a result, three alogrithms are presented and their performance compared on a number of problems originally tested by Beasley (1984, 1987) in the case of undirected graphs. [ABSTRACT FROM AUTHOR]