Optimization Online


A Linear Programming Based Approach to the Steiner Tree Problem with a Fixed Number of Terminals

Matias Siebert(msiebert6***at***gatech.edu)
Shabbir Ahmed(shabbir.ahmed***at***isye.gatech.edu)
George Nemhauser(gn3***at***gatech.edu)

Abstract: We present a set of integer programs (IPs) for the Steiner tree problem with the property that the best solution obtained by solving all, provides an optimal Steiner tree. Each IP is polynomial in the size of the underlying graph and our main result is that the linear programming (LP) relaxation of each IP is integral so that it can be solved as a linear program. However, the number of IPs grows exponentially with the number of terminals in the Steiner tree. As a consequence, we are able to solve the Steiner tree problem by solving a polynomial number of LPs, when the number of terminals is fixed.

Keywords: Steiner tree, Integer programming, Linear programming, Laminar family

Category 1: Network Optimization

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA

Download: [PDF]

Entry Submitted: 12/05/2018
Entry Accepted: 12/23/2018
Entry Last Modified: 12/05/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society