MPI-INF Logo
MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1

MPI-I-2003-1-004

Improving linear programming approaches for the Steiner tree problem

Althaus, Ernst and Polzin, Tobias and Daneshmand, Siavash Vahdati

March 2003, 19 pages.

.
Status: available - back from printing

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.
Categories / Keywords:
Steiner problem; Lower Bounds; Linear Programming; Local Cuts

  • MPI-I-2003-1-004.ps
  • Attachement: MPI-I-2003-1-004.ps (359 KBytes)

URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2003-1-004

Hide details for BibTeXBibTeX
@TECHREPORT{AlthausPolzinDaneshmand2003,
  AUTHOR = {Althaus, Ernst and Polzin, Tobias and Daneshmand, Siavash Vahdati},
  TITLE = {Improving linear programming approaches for the Steiner tree problem},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2003-1-004},
  MONTH = {March},
  YEAR = {2003},
  ISSN = {0946-011X},
}