Steiner Tree Problem in Graphs and Mixed Integer Linear Programming-Based Approach in GAMS
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F22%3APU146097" target="_blank" >RIV/00216305:26210/22:PU146097 - isvavai.cz</a>
Výsledek na webu
<a href="https://wseas.com/journals/computers/2022/a625105-028(2022).pdf" target="_blank" >https://wseas.com/journals/computers/2022/a625105-028(2022).pdf</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.37394/23205.2022.21.31" target="_blank" >10.37394/23205.2022.21.31</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Steiner Tree Problem in Graphs and Mixed Integer Linear Programming-Based Approach in GAMS
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Steiner Tree Problem in Graphs and Mixed Integer Linear Programming-Based Approach in GAMS
Popis výsledku anglicky
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.
Klasifikace
Druh
J<sub>ost</sub> - Ostatní články v recenzovaných periodicích
CEP obor
—
OECD FORD obor
10102 - Applied mathematics
Návaznosti výsledku
Projekt
—
Návaznosti
S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2022
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
WSEAS Transactions on Computers
ISSN
1109-2750
e-ISSN
—
Svazek periodika
21
Číslo periodika v rámci svazku
July
Stát vydavatele periodika
GR - Řecká republika
Počet stran výsledku
6
Strana od-do
257-262
Kód UT WoS článku
—
EID výsledku v databázi Scopus
—