Improved algorithms for the Steiner problem in networks (Q5946826)

The paper gives several new techniques for dealing with the Steiner problem in networks. Certain relaxations of integer programming formulations are presented. Different methods for dealing these relaxations yield lower bounds and additional information which is used in computation of upper bounds and in reduction techniques. The authors modify some known reduction tests and introduce some new ones. On the basis of the new concept of heuristic reductions heuristics are developed that achieve good upper bounds and running times. A Lagrangean relaxation and the above procedures are integrated into an exact algorithm. Computational results demonstrate the superiority of this algorithm to other ones.