Bounds for global optimization of capacity expansion and flow assignment problems

This paper provides new bounds related to the global optimization of the problem of mixed routing and bandwidth allocation in telecommunication systems. The combinatorial nature of the problem, related to arc expansion decisions, is embedded in a continuous objective function that encompasses congestion and investment line costs. It results in a non-convex multicommodity flow problem, but we explore the separability of the objective function and the fact that each associated arc cost function is piecewise-convex. Convexifying each arc cost function enables the use of efficient algorithms for convex multicommodity flow problems, and we show how to calculate sharp bounds for the approximated solutions.