Branch-and-Price Algorithm for a Multicast Routing Problem

This paper considers a multicast routing problem to find the minimum cost tree where the whole communication link delay on each path(route) of the tree is subject to a given delay allowance. The problem is formulated as an integer programming problem by using path variables. An associated problem reduction property is then characterised to reduce the solution space. Moreover, a polynomial time column generation procedure is exploited to solve the associated linear programming relaxation with such solution space reduced. Therefore a branch-and-price algorithm is derived to obtain the optimal integer solution(tree) for the problem. Computational results show that the algorithm can solve practical size problems in a reasonable length of time.
Publisher
Palgrave Macmillan Ltd
Issue Date
1999-11
Language
ENG
Keywords

NETWORKS; DELAY; COMMUNICATION

Citation

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, v.50, no.11, pp.1168 - 1175

ISSN
0160-5682
URI
http://hdl.handle.net/10203/73383
Appears in Collection
IE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
  • Hit : 113
  • Download : 0
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 7 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0