hide
Free keywords:
-
Abstract:
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.
