Detail publikace
Metoda simulovaného žíhání pro řešení problému celočíselného maximálního víceproduktového toku v síti
ŠEDA, M.
Český název
Metoda simulovaného žíhání pro řešení problému celočíselného maximálního víceproduktového toku v síti
Anglický název
A Simulated Annealing Approach for Integer Maximal Multicommodity Flow Problem
Typ
článek ve sborníku ve WoS nebo Scopus
Jazyk
en
Originální abstrakt
In this paper the Integer Maximal Multicommodity Flow Problem is discussed. It belongs to the class of NP-hard combinatorial problems and thus for large scale instances must be solved by approximation or heuristic techniques. Many techniques for solving these problems are based on various decomposition algorithms, cutting plane methods and Lagrangean relaxation usually used for integer programming problems. We propose quite a different approach based on simulated annealing where all evaluations of the objective function are provided by an allocation procedure.
Český abstrakt
V příspěvku je studován problém celočíselného maximálního víceproduktového toku v síti. Tento problém patří do třídy NP-těžkých kombinatorických problémů, a proto pro velké rozsahy vstupních dat musí být řešen aproximativními nebo heuristickými technikami. Mnoho z nich je založeno na různých dekompozičních algoritmech, metodě řezných plánů a Lagrangeově relaxační metodě, které jsou používány pro řešení problémů celočíselného programování. Navrhujeme zcela odlišný přístup založený na simulovaném žíhání, kde všechny výpočty účelové funkce se provádí pomocí speciální alokační procedury.
Anglický abstrakt
In this paper the Integer Maximal Multicommodity Flow Problem is discussed. It belongs to the class of NP-hard combinatorial problems and thus for large scale instances must be solved by approximation or heuristic techniques. Many techniques for solving these problems are based on various decomposition algorithms, cutting plane methods and Lagrangean relaxation usually used for integer programming problems. We propose quite a different approach based on simulated annealing where all evaluations of the objective function are provided by an allocation procedure.
Klíčová slova anglicky
multicommodity network flow, stochastic heuristic, simulated annealing
Vydáno
01.09.2004
Nakladatel
University of Zenica
Místo
Neum (Bosnia and Herzegovina)
ISBN
9958-617-21-8
Kniha
Proceedings of the 8th International Research/Expert Conference Trends in the Development of Machinery and Associated Technology TMT 2004
Počet stran
4
BIBTEX
@inproceedings{BUT12864,
author="Miloš {Šeda},
title="A Simulated Annealing Approach for Integer Maximal Multicommodity Flow Problem",
booktitle="Proceedings of the 8th International Research/Expert Conference Trends in the Development of Machinery and Associated Technology TMT 2004",
year="2004",
month="September",
publisher="University of Zenica",
address="Neum (Bosnia and Herzegovina)",
isbn="9958-617-21-8"
}