Branch-and-price algorithm for a combined problem of virtual path establishment and traffic packet routing in a layered communication network

Branch-and-price algorithm for a combined problem of virtual path establishment and traffic packet routing in a layered communication network

0.00 Avg rating0 Votes
Article ID: iaor20032035
Country: United Kingdom
Volume: 54
Issue: 1
Start Page Number: 72
End Page Number: 82
Publication Date: Jan 2003
Journal: Journal of the Operational Research Society
Authors: ,
Keywords: communications
Abstract:

This paper considers a combined problem of establishing virtual paths (VPs) and routing traffic (packet) demands through the virtual paths in a layered communication network where each physical link is subject to its capacity constraints. The problem is modeled as a path-based formulation for which a branch-and-price solution algorithm is derived. The solution algorithm is composed of an efficient pricing algorithm, and also a branching rule based on a variable dichotomy, which does not destroy the structure of the associated pricing problems. Computational experiments are performed to test the efficiency of the algorithm, which show that the algorithm works quite well in finding optimal solutions (for the test instances) within reasonable time. Its immediate application may be made to a centralized network management on mid-term global reconfiguration and long-term VP planning.

Reviews

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