Optimal expansion of an existing network

Given an existing network, a list of arcs which could be added to the network, the arc costs and capacities, and an available budget, the problem considered in this paper is one of choosing which arcs to add to the network in order to maximize the maximum flow from a sources to a sinkt, subject to the budgetary constraint. This problem appears in a large number of practical situations which arise in connection with the expansion of electricity or gas supply, telephone, road or rail networks. The paper describes an efficient tree-search algorithm using bounds calculated by a dynamic programming procedure which are very effective in limiting the solution space explicitly searched. Computational results for a number of medium sized problems are described and computing times are seen to be very reasonable.