Repository logo
 

Algorithms for multicommodity network flow problems

Loading...
Thumbnail Image

Date

1999

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

Citation

Collections