The Steiner problem in networks is the problem of connecting a set of required vertices in a weighted graph at minimum cost. This is a classical NP-hard problem and a fundamental problem in network design with many practical applications. We approach this problem by various means: Relaxations, which relax the feasibility constraints, to get close to an optimal solution; heuristics to find good, but not necessarily optimal solutions; and reductions to simplify problem instances without abandoning the optimal solution. We have integrated these components into an exact algorithm that has achieved outstanding results in practice. In this article, we first provide a brief overview on the main algorithmic developments related to our work on this problem, citing our and others (already published) works. Then we focus on some central concepts, presenting detailed results on selected topics that offer special insight and potential for further improvement.
There are many (mixed) integer programming formulations of the Steiner problem in networks. The corresponding linear programming relaxations are of great interest particularly, but not exclusively, for computing lower bounds; but not much has been known about the relative quality of these relaxations. We compare all classical and some new relaxations from a theoretical point of view with respect to their optimal values. Among other things, we prove that the optimal value of a flow-class relaxation (e.g. the multicommodity flow or the dicut relaxation) cannot be worse than the optimal value of a tree-class relaxation (e.g. degree-constrained spanning tree relaxation) and that the ratio of the corresponding optimal values can be arbitrarily large. Furthermore, we present a new flow based relaxation, which is to the authors' knowledge the strongest linear relaxation of polynomial size for the Steiner problem in networks.
We present several new techniques for dealing with the Steiner problem in (undirected) networks. We consider them as building blocks of an exact algorithm, but each of them could also be of interest in its own right. First, we consider some relaxations of integer programming formulations of this problem and investigate different methods for dealing with these relaxations, not only to obtain lower bounds, but also to get additional information which is used in the computation of upper bounds and in reduction techniques. Then, we modify some known reduction tests and introduce some new ones. We integrate some of these tests into a package with a small worst case time which achieves impressive reductions on a wide range of instances. On the side of upper bounds, we introduce the new concept of heuristic reductions. On the basis of this concept, we develop heuristics that achieve sharper upper bounds than the strongest known heuristics for this problem despite running times which are smaller by orders of magnitude. Finally, we integrate these blocks into an exact algorithm. We present computational results on a variety of benchmark instances. The results are clearly superior to those of all other exact algorithms known to the authors.
The bottleneck of the state-of-the-art algorithms for geometric Steiner problems is usually the concatenation-phase, where the prevailing approach treats the generated full Steiner trees as edges of a hypergraph and uses an LP-relaxation of the minimum spanning tree in hypergraph (MSTH) problem. We study this original and some new equivalent relaxations of this problem and clarify their relations to all classical relaxations of the Steiner problem. In an experimental study, an algorithm of ours which is designed for general graphs turns out to be an efficient alternative to the MSTH approach.
We study several old and new algorithms for computing lower and upper bounds for the Steiner problem in networks using dual-ascent and primal-dual strategies. We show that none of the known algorithms can both generate tight lower bounds empirically and guarantee their quality theoretically; and we present a new algorithm which combines both features. The new algorithm has running time O(re\log n) and guarantees a ratio of at most two between the generated upper and lower bounds, whereas the fastest previous algorithm with comparably tight empirical bounds has running time O(e^2) without a constant approximation ratio. Furthermore, we show that the approximation ratio two between the bounds can even be achieved in time O(e + n\log n), improving the previous time bound of O(n^2\log n).
Reduction methods are a key ingredient of the most successful algorithms for the Steiner problem. Whereas classical reduction tests just considered single vertices or edges, recent and more sophisticated tests extend the scope of inspection to more general patterns. In this paper, we present such an extended reduction test, which generalizes different tests in the literature. We use the new approach of combining alternative- and bound-based methods, which substantially improves the impact of the tests. We also present several algorithmic contributions. The experimental results show a large improvement over previous methods using the idea of extension, leading to a drastic speed-up in the optimal solution process and the solution of several previously unsolved benchmark instances.
We present two theoretically interesting and empirically successful techniques for improving the linear programming approaches, namely graph transformation and local cuts, in the context of the Steiner problem. We show the impact of these techniques on the solution of the largest benchmark instances ever solved.
Partitioning is one of the basic ideas for designing efficient algorithms, but on NP-hard problems like the Steiner problem, straightforward application of the classical partitioning-based paradigms rarely leads to empirically successful algorithms. In this paper, we present two approaches to the Steiner problem based on partitioning. The first uses the fixed-parameter tractability of the problem with respect to a certain width parameter closely related to path-width. The second approach is based on vertex separators and is new in the sense that it uses partitioning to design reduction methods. Integrating these methods into our program package for the Steiner problem accelerates the solution process on many groups of instances and leads to a fast solution of some previously unsolved benchmark instances.