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 algorithms are presented and their performance compared on a number of problems originally tested by Beasely in the case of undirected graphs.