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

Sunil Chopra*, M. R. Rao

*Corresponding author for this work

Research output: Contribution to journalArticle

77 Scopus citations

Abstract

In this paper we give some integer programming formulations for the Steiner tree problem on undirected and directed graphs and study the associated polyhedra. We give some families of facets for the undirected case along with some compositions and extensions. We 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.

Original languageEnglish (US)
Pages (from-to)209-229
Number of pages21
JournalMathematical Programming
Volume64
Issue number1-3
DOIs
StatePublished - Mar 1 1994

Keywords

  • Facets
  • Polyhedron
  • Projection
  • Steiner tree

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'The Steiner tree problem I: Formulations, compositions and extension of facets'. Together they form a unique fingerprint.

  • Cite this