Bounds for global optimization of capacity expansion and flow assignment problems

This paper provides new bounds related to the global optimization of the pr oblem of mixed routing and bandwidth allocation in telecommunication system s. The combinatorial nature of the problem, related to are expansion decisi ons, is embedded in a continuous objective function that encompasses conges tion and investment line costs. It results in a non-convex multicommodity f low problem, but we explore the separability of the objective function and the fact that each associated are cost function is piecewise-convex. Convex ifying each are cost function enables the use of efficient algorithms for c onvex multicommodity flow problems, and we show how to calculate sharp boun ds for the approximated solutions. (C) 2000 Elsevier Science B.V. All right s reserved.