Publication detail

Steiner Tree Problem in Graphs and Mixed Integer Linear Programming-Based Approach in GAMS

ŠEDA, M.

Original Title

Steiner Tree Problem in Graphs and Mixed Integer Linear Programming-Based Approach in GAMS

Type

journal article - other

Language

English

Original Abstract

The Steiner tree problem in graphs involves finding a minimum cost tree which connects a defined subset of the vertices. This problem generalises the minimum spanning tree problem, in contrast, it is NP-complete and is usually solved for large instances by deterministic or stochastic heuristic methods and approximate algorithms. In this paper, however, we focus on a different approach, based on the formulation of a mixed integer programming model and its modification for solving in the professional optimization tool GAMS, which is now capable of solving even large instances of problems of exponential complexity.

Keywords

Steiner tree problem, NP-completeness, heuristic, performance ratio, network flow, mixed-integer linear programming, GAMS

Authors

ŠEDA, M.

Released

1. 7. 2022

Publisher

WSEAS

ISBN

1109-2750

Periodical

WSEAS Transactions on Computers

Year of study

21

Number

July

State

Hellenic Republic

Pages from

257

Pages to

262

Pages count

6

URL

https://wseas.com/journals/computers/2022/a625105-028(2022).pdf

BibTex

@article{BUT179804,
  author="Miloš {Šeda}",
  title="Steiner Tree Problem in Graphs and Mixed Integer Linear Programming-Based Approach in GAMS",
  journal="WSEAS Transactions on Computers",
  year="2022",
  volume="21",
  number="July",
  pages="257--262",
  doi="10.37394/23205.2022.21.31",
  issn="1109-2750",
  url="https://wseas.com/journals/computers/2022/a625105-028(2022).pdf"
}