Tutoriel : Multicommodity flow networks with convex and nonconvex arc cost functions
Philippe Mahey  1@  
1 : Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes  (LIMOS)  -  Website
Université Blaise Pascal - Clermont-Ferrand II, CNRS : UMR6158
Bât ISIMA Campus des Cézeaux BP 10025 63173 AUBIERE cedex -  France

Multicommodity flow networks are known to be much harder than single-commodity problems, even in the linear case and even when no more than two commodities have to share the same network. On the other hand, network design problems in telecommunications networks are frequently modelled by multicommodity flows, indeed one for each origin-destination pairs. We review here the main difficulties and solution strategies, from the linear and convex cost functions to nonconvex arc cost functions and mixed-integer nonlinear multicommodity flow networks. We illustrate the algorithmic issues on a capacity expansion problem with congestion costs.


Online user: 2