Detail publikačního výsledku

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

ŠEDA, M.

Originální název

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

Anglický název

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

Druh

Článek recenzovaný mimo WoS a Scopus

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

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

Klíčová slova v angličtině

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

Autoři

ŠEDA, M.

Rok RIV

2023

Vydáno

01.07.2022

Nakladatel

WSEAS

ISSN

1109-2750

Periodikum

WSEAS Transactions on Computers

Svazek

21

Číslo

July

Stát

Řecká republika

Strany od

257

Strany do

262

Strany počet

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"
}