Algorithms for multicommodity network flow problems

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.