Solving the Steiner tree problem on a graph using branch and cut

Sunil Chopra; Edgar R. Gorres; M. R. Rao

doi:10.1287/ijoc.4.3.320

Solving the Steiner tree problem on a graph using branch and cut

Sunil Chopra^*, Edgar R. Gorres, M. R. Rao

^*Corresponding author for this work

Managerial Economics, Decision Sciences and Operations

Research output: Contribution to journal › Article › peer-review

64 Scopus citations

Abstract

In this paper we report computational experience with a branch and cut solver for the Steiner tree problem on a graph. The problem instances include complete graphs, randomly generated sparse graphs and grid graphs. The edge weights are either randomly generated or are the Euclidean distance between the endnodes that are placed at random on the plane. The effect of changing various problem parameters on solution time is studied.

Original language	English (US)
Pages (from-to)	320-335
Number of pages	16
Journal	ORSA journal on computing
Volume	4
Issue number	3
DOIs	https://doi.org/10.1287/ijoc.4.3.320
State	Published - Jan 1 1992

ASJC Scopus subject areas

General Engineering

Access to Document

10.1287/ijoc.4.3.320

Cite this

@article{12bdfc5231ed486199d65621e5d68645,

title = "Solving the Steiner tree problem on a graph using branch and cut",

abstract = "In this paper we report computational experience with a branch and cut solver for the Steiner tree problem on a graph. The problem instances include complete graphs, randomly generated sparse graphs and grid graphs. The edge weights are either randomly generated or are the Euclidean distance between the endnodes that are placed at random on the plane. The effect of changing various problem parameters on solution time is studied.",

author = "Sunil Chopra and Gorres, {Edgar R.} and Rao, {M. R.}",

year = "1992",

month = jan,

day = "1",

doi = "10.1287/ijoc.4.3.320",

language = "English (US)",

volume = "4",

pages = "320--335",

journal = "ORSA journal on computing",

issn = "0899-1499",

publisher = "INFORMS Institute for Operations Research and the Management Sciences",

number = "3",

}

TY - JOUR

T1 - Solving the Steiner tree problem on a graph using branch and cut

AU - Chopra, Sunil

AU - Gorres, Edgar R.

AU - Rao, M. R.

PY - 1992/1/1

Y1 - 1992/1/1

N2 - In this paper we report computational experience with a branch and cut solver for the Steiner tree problem on a graph. The problem instances include complete graphs, randomly generated sparse graphs and grid graphs. The edge weights are either randomly generated or are the Euclidean distance between the endnodes that are placed at random on the plane. The effect of changing various problem parameters on solution time is studied.

AB - In this paper we report computational experience with a branch and cut solver for the Steiner tree problem on a graph. The problem instances include complete graphs, randomly generated sparse graphs and grid graphs. The edge weights are either randomly generated or are the Euclidean distance between the endnodes that are placed at random on the plane. The effect of changing various problem parameters on solution time is studied.

UR - http://www.scopus.com/inward/record.url?scp=0026880297&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026880297&partnerID=8YFLogxK

U2 - 10.1287/ijoc.4.3.320

DO - 10.1287/ijoc.4.3.320

M3 - Article

AN - SCOPUS:0026880297

SN - 0899-1499

VL - 4

SP - 320

EP - 335

JO - ORSA journal on computing

JF - ORSA journal on computing

IS - 3

ER -

Solving the Steiner tree problem on a graph using branch and cut

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this