Capacitated Network Design: Exact Algorithms, Reformulations and the Convex Hull

We study exact algorithms for several variations of the capacitated network design problem, all of which are known to be NP-hard. Exact algorithms are useful for telecommunication network design since the cost of installing networks is very high, and optimal solutions could provide substantial cost savings compared to heuristic solutions. We describe an O(n22n) implicit tree enumeration algorithm and an O(n22k+n3k) dynamic programming path based algorithm where n is the number of nodes and K the number of terminals that need to be connected. In general, the worst case running times of the two algorithms are the same for capacitated and uncapacitated problems, and surprisingly, are faster for problem instances where the capacity constraint on edges is very tight. We also describe the convex hull of feasible integer solutions using O(m2k+n3k) variables and O(n2k) constraints, which is polynomial for fixed K. Finally we show how to use these algorithms to solve a wide variety of related problems, including those with node capacities, the concentrator locator and capacitated plant location problems, a variant of the network loading problem, network expansion, i.e., adding nodes and edges to an existing network, the two level network design problem, and the problem of long term planning where the network is expanded over several years.