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