An Algorithm for the Design of Multitype Concentrator Networks
作者:
LeeChoong Y.,
期刊:
Journal of the Operational Research Society
(Taylor Available online 1993)
卷期:
Volume 44,
issue 5
页码: 471-482
ISSN:0160-5682
年代: 1993
DOI:10.1057/jors.1993.83
出版商: Taylor&Francis
关键词: Concentrator Location;Cross Decomposition
数据来源: Taylor
摘要:
AbstractIn recent years we have witnessed remarkable progress in the development of the topological design of computer communication networks. One of the important aspects of the topological design of computer communication networks is the concentrator location problem. This problem is a complex combinatorial problem that belongs to the difficult class of NP-complete problems where the computation of an optimal solution is still a challenging task. This paper extends the standard capacitated concentrator location problem to a generalization of multitype capacitated concentrator location problems and presents an efficient algorithm based on cross decomposition. This algorithm incorporates the Benders decomposition and Lagrangean relaxation methods into a single framework and exploits the resulting primal and dual structure simultaneously. Computational results are quite satisfactory and encouraging and show this algorithm to be both efficient and effective. The use of cross decomposition as a heuristic algorithm is also discussed.
点击下载:
PDF (5382KB)
返 回