This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Salman, F. S. Articles by Hooker, J. N. Search for Related Content

Solving the Capacitated Local Access Network Design Problem

College of Engineering, Koç University, Istanbul 34450, Turkey
Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
ssalman{at}ku.edu.tr
ravi{at}cmu.edu
john{at}hooker.tepper.cmu.edu

We propose an exact solution method for a routing and capacity installation problem in networks. Given an input graph, the problem is to route traffic from a set of source nodes to a sink node and to install transmission facilities on the edges of the graph to accommodate the flow at minimum cost. We give a branch-and-bound algorithm that solves relaxations obtained by approximating the noncontinuous cost function by its lower convex envelope. The approximations are refined by branching on the flow ranges on selected edges. Our computational experiments indicate that this method is effective in solving moderate-size problems and provides very good candidate solutions early in the branch-and-bound tree.

Key words: network design; routing flow; capacity installation; branch and bound
History: received August 2001; revised February 2007; accepted June 2007.