An exact algorithm for the network synthesis problem

This paper studies the network synthesis problem, which is common in the design of telecommunication networks and considers a set of practical constraints, such as arc capacity, node capacity and degree, and hop limit. To obtain the minimum cost for the given traffic flows, we propose a concretized model and a branch and bound algorithm for the problem. A schema based on Lagrangian relaxation is introduced for tight lower bounds. Computational experiments were performed using a group of randomly generated problems. The results demonstrate the effectiveness of the proposed exact algorithm for small size problems.