Dual ascent for uncapacitated telecommunications network design with access, backbone, and switch costs

We consider the telecommunications network design problem of simultaneously determining at which locations to place a switch, interconnecting all swit ches with backbone trunks, and connecting each location to some switch by a n access circuit. We assume there are no capacity constraints, and minimize the sum of switch, backbone trunk, and access circuit costs using a dual a scent 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% .