Global Optimum Search in the Network Design Problem

The global optimum search in the network design problem for the case of networks with disjoint paths is considered. In the considered formulation of the problem, the manager of a network invests in the capacities of its elements, seeking to minimize the total delay arising from the equilibrium flow assignment. It is proven that the solution to the problem under study must necessarily solve a certain minimax problem. Optimality conditions for solutions of the minimax problem are found under fairly natural assumptions. Based on the results, a new algorithm is developed for optimizing the topology of a network with disjoint paths.