Branch-and-price algorithm for a multicast routing problem

Branch-and-price algorithm for a multicast routing problem

0.00 Avg rating0 Votes
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: ,
Keywords: networks
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.