|
|
Digital Library of the
European Council for Modelling and Simulation |
|
Title: |
Network
Flows In Optimisation Problems And Their Extensions |
|
Authors: |
Milos Seda |
|
Published in:
|
(2010).ECMS 2010 Proceedings
edited by A Bargiela S A Ali D Crowley E J H Kerckhoffs. European Council for Modeling and Simulation.
doi:10.7148/2010 ISBN:
978-0-9564944-1-2 24th
European Conference on Modelling and Simulation, Simulation Meets Global Challenges Kuala
Lumpur, June 1-4 2010 |
|
Citation
format: |
Seda, M. (2010). Network Flows In Optimisation Problems And Their Extensions. ECMS 2010
Proceedings edited by A Bargiela S A Ali D Crowley
E J H Kerckhoffs (pp. 271-276). European Council
for Modeling and Simulation. doi:10.7148/2010-0271-0276 |
|
DOI: |
http://dx.doi.org/10.7148/2010-0271-0276 |
|
Abstract: |
Network flow problems are among the most important ones in
graph theory. Since there are many well-known polynomial algorithms for
solving the classical Maximum Flow Problem, we, instead of summarising them, focus on special formulations and their
transformation into the basic one, and because other graph theory problems
may be formulated with the help of network flow tools, we show how to
formulate the Minimum Steiner Tree Problem using the maximum network flow
terminology and derive its mathematical model. Finally,
we discuss the Integer Maximal Multi- commodity Flow Problem. Since this
network flow version belongs to the class of NP-hard combinatorial problems,
for large scale instances, it must be solved by approximation or heuristic
techniques. We present a stochastic heuristic approach based on a simulated
annealing algorithm. |
|
Full
text: |
|
