Gavish, Bezalel; Altinkemer, Kemal Backbone network design tools with economics tradeoffs. (English) Zbl 0755.90024 ORSA J. Comput. 2, No. 3, 236-252 (1990). 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. Cited in 26 Documents 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 Keywords:backbone network; routing and link capacities; lower bounds; Lagrangian relaxation; subgradient optimization; heuristic method PDFBibTeX XMLCite \textit{B. Gavish} and \textit{K. Altinkemer}, ORSA J. Comput. 2, No. 3, 236--252 (1990; Zbl 0755.90024) Full Text: DOI