Mathematical programming approaches for dual multicast routing problem   with multilayer risk cost

doi:10.1007/s10479-013-1317-4

CORC > 北京大学 > 工学院

	Mathematical programming approaches for dual multicast routing problem with multilayer risk cost
	Liang, Zhe ; Lee, Chungmok ; Chaovalitwongse, W. Art
刊名	annals of operations research
	2013
关键词	Mixed integer program Telecommunication Multicast Shared risk link groups Multi-objective WDM MESH NETWORKS LAYER CONSTRAINTS COLUMN GENERATION PROTECTION PATH REDUNDANT ALGORITHM DESIGN GRAPHS MODELS
DOI	10.1007/s10479-013-1317-4
英文摘要	This paper addresses a dual multicast routing problem with shared risk link group (SRLG) diverse costs (DMR-SRLGD) that arises from large-scale distribution of realtime multicast data (e.g., internet protocol TV, videocasting, online games, stock price update). The goal of this problem is to find two redundant multicast trees, each from one of the two sources to every destination at a minimum cost. The cost of the problem contains two parts: the multicast routing cost and the shard common risk cost. Such common risk could cause the failures of multiple links simultaneously. Therefore, the DMR-SRLGD ensures the availability and reliability of multicast service. We formulate an edge-based model for the DMR-SRLGD. In addition, we also propose a path-based model that rises from the Dantzig-Wolfe decomposition of the edge-based model, and develop a column-generation framework to solve the linear relaxation of the path-based formulation. We then employ a branch-and-price solution method to find integer solutions to DMR-SRLGD. We also extend both edge-based and path-based models to handle the complex quality of service requirements. The computational results show the edge-based model is superior than the path-based model for the easy and small test instances, whereas the path-based model provides better solutions in a timely fashion for hard or large test instances.; Operations Research & Management Science; SCI(E); 0; ARTICLE; 1; 101-118; 203
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/226665]
专题	工学院
推荐引用方式 GB/T 7714	Liang, Zhe,Lee, Chungmok,Chaovalitwongse, W. Art. Mathematical programming approaches for dual multicast routing problem with multilayer risk cost[J]. annals of operations research,2013.
APA	Liang, Zhe,Lee, Chungmok,&Chaovalitwongse, W. Art.(2013).Mathematical programming approaches for dual multicast routing problem with multilayer risk cost.annals of operations research.
MLA	Liang, Zhe,et al."Mathematical programming approaches for dual multicast routing problem with multilayer risk cost".annals of operations research (2013).