Solving the Uncapacitated Network Design Problem by a Lagrangean Heuristic and Branch-and-Bound

The network design problem is a multicommodity minimal cost network flow problem with fixed costs on the arcs, i.e., a structured linear mixed-integer programming problem. It has various applications, such as construction of new links in transportation networks, topological design of computer communication networks, and planning of empty freight car transportation on railways. We present a Lagrangean heuristic within a branch-and-bound framework as a method for finding the exact optimal solution of the uncapacitated network design problem with single origins and destinations for each commodity (the simplest problem in this class, but still NP-hard). The Lagrangean heuristic uses a Lagrangean relaxation as subproblem, solving the Lagrange dual with subgradient optimization, combined with a primal heuristic (the Benders subproblem) yielding primal feasible solutions. Computational tests on problems of various sizes (up to 1000 arcs, 70 nodes and 138 commodities or 40 nodes and 600 commodities) and of several different structures lead to the conclusion that the method is quite powerful, outperforming for example a state-of-the-art mixed-integer code, both with respect to problem size and solution time.