Article ID: | iaor20003247 |
Country: | United Kingdom |
Volume: | 50 |
Issue: | 11 |
Start Page Number: | 1168 |
End Page Number: | 1175 |
Publication Date: | Nov 1999 |
Journal: | Journal of the Operational Research Society |
Authors: | Sung C.S., Hong J.M. |
Keywords: | networks |
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.