An Ezact 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.
branch and bound search tree pruning Lagrangian Relazation combinatorial optimization
Jun Han Ming Lei Xin Wei Yaling Huang
School of Computer Science & Engineering, Beihang University, Beijing, China School of Automation Science & Electrical Engineering, Beihang University, Beijing, China
国际会议
北京
英文
963-969
2009-08-08（万方平台首次上网日期，不代表论文的发表时间）