×

Backbone network design tools with economics tradeoffs. (English) Zbl 0755.90024

Summary: This paper studies the problem of assigning capacities to the links in a backbone network and determining the primary routes used by messages for each origin-destination communicating pair in the network. The topology of the backbone network is assumed to be known and the end to end traffic requirements are given. The problem is to find the least cost design where the system costs are composed of connection costs which depend on link capacities and queueing costs which are incurred by users due to the limited capacities of links. The goal is to determine the routing and link capacities simultaneously. The problem is formulated and lower bounds are obtained by Lagrangian relaxation embedded in a subgradient optimization procedure. Cut constraints which are redundant in the original formulation are introduced, they improve the lower bounds. A heuristic method based on the Lagrangian solution is described. Extensive computational results are reported.

MSC:

90B18 Communication networks in operations research
90C90 Applications of mathematical programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI