The Steiner problem I: Formulations, compositions and extension of facets

The Steiner problem I: Formulations, compositions and extension of facets

0.00 Avg rating0 Votes
Article ID: iaor19961319
Country: Netherlands
Volume: 64
Issue: 2
Start Page Number: 209
End Page Number: 229
Publication Date: Apr 1994
Journal: Mathematical Programming (Series A)
Authors: ,
Keywords: Steiner problem
Abstract:

In this paper the authors give some integer programming formulations for the Steiner tree problem on undirected and directed graphs and study the associated polyhedra. They give some families of facets for the undirected case along with some compositions and extensions. The authors also give a projection that relates the Steiner tree polyhedron on an undirected graph to the polyhedron for the corresponding directed graph. This is used to show that the LP-relaxation of the directed formulation is superior to the LP-relaxation of the undirected one.

Reviews

Required fields are marked *. Your email address will not be published.