Detail publikace

Steinerův problém v grafech a přístup založený na modelu smíšeného celočíselného programování v GAMSu

ŠEDA, M.

Český název

Steinerův problém v grafech a přístup založený na modelu smíšeného celočíselného programování v GAMSu

Anglický název

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

Typ

článek v časopise - ostatní, Jost

Jazyk

en

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.

Český abstrakt

Steinerův problém v grafech spočívá v nalezení nejkratšího stromu, který spojuje definovanou podmnožinu vrcholů. Tento problém zobecňuje problém minimální kostry grafu, na rozdíl od něj je NP-úplný a pro velké instance se obvykle řeší deterministickými nebo stochastickými heuristickými metodami a aproximativními algoritmy. V tomto článku se však zaměříme na jiný přístup, založený na formulaci modelu smíšeného celočíselného programování a jeho modifikaci pro řešení v profesionálním optimalizačním nástroji GAMS, který je nyní schopen řešit i velké instance problémů exponenciální složitosti.

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 česky

Steinerův problém, NP-úplnost, heuristika, Steinerův poměr, tok v síti, smíšené celočíslené programování, GAMS

Klíčová slova anglicky

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

Vydáno

01.07.2022

Nakladatel

WSEAS

ISSN

1109-2750

Ročník

21

Číslo

July

Strany od–do

257–262

Počet stran

6

BIBTEX


@article{BUT179804,
  author="Miloš {Šeda},
  title="Steiner Tree Problem in Graphs and Mixed Integer Linear Programming-Based Approach in GAMS",
  year="2022",
  volume="21",
  number="July",
  month="July",
  pages="257--262",
  publisher="WSEAS",
  issn="1109-2750"
}