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 conges...

Full description

Saved in:
Bibliographic Details
Published in:Operations research letters 2000-06, Vol.26 (5), p.211-216
Main Authors: Luna, H.P.L., Mahey, P.
Format: Article
Language:English
Subjects:
Capacity expansion of telecommunication systems
Network design
Nonconvex multicommodity flow problem
Separable convexification
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0167-6377
1872-7468
DOI:10.1016/S0167-6377(00)00027-4