Přístupnostní navigace
E-přihláška
Vyhledávání Vyhledat Zavřít
Detail publikace
ŠEDA, M.
Originální název
Steiner Tree Problem in Graphs and Mixed Integer Linear Programming-Based Approach in GAMS
Typ
článek v časopise - ostatní, Jost
Jazyk
angličtina
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.
Klíčová slova
Steiner tree problem, NP-completeness, heuristic, performance ratio, network flow, mixed-integer linear programming, GAMS
Autoři
Vydáno
1. 7. 2022
Nakladatel
WSEAS
ISSN
1109-2750
Periodikum
WSEAS Transactions on Computers
Ročník
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" }