Article
Dual Ascent for Uncapacitated Telecommunications Network Design with Access, Backbone, and Switch Costs
Telecommunication Systems
(2001)
Abstract
We consider the telecommunications network design problem of simultaneously determining at which locations to place a switch, interconnecting all switches with backbone trunks, and connecting each location to some switch by an access circuit. We assume there are no capacity constraints, and minimize the sum of switch, backbone trunk, and access circuit costs using a dual ascent method that solves a sequence of dual uncapacitated facility location problems. A Steiner tree based heuristic provides a primal feasible design. On 15 random problems with 100 locations, the average duality gap is 2.0%.
Keywords
- telecommunications,
- network,
- design,
- dual ascent,
- uncapacitated
Disciplines
Publication Date
March, 2001
DOI
10.1023/A:1016623229800
Citation Information
Eric Rosenberg. "Dual Ascent for Uncapacitated Telecommunications Network Design with Access, Backbone, and Switch Costs" Telecommunication Systems Vol. 16 (2001) p. 423 - 435 ISSN: 1572-9451 Available at: http://works.bepress.com/eric-rosenberg/31/