Algorithms for multicommodity network flow problems
Loading...
Date
1999
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Te Herenga Waka—Victoria University of Wellington
Abstract
Multicommodity network flow problems arise in real life in telecommunications network design, transportation network design, etc. All commodities use the same capacitated communication/transportation channel. These problems are usually very large. Hence general purpose linear algorithms which do not exploit the special structure of the networks become inefficient. Moreover, sometimes the objective function can be non-linear.
In this thesis we have discussed two types of formulation of the problem namely arc flow formulation and path flow formulation. We have discussed several algorithms for solution including optimal and heuristic methods. A problem with non-integer objective function has been discussed. Numerical examples have been included where appropriate.
Description
Keywords
Network analysis, Programming in mathematics