Branch-and-price algorithm for a combined problem of virtual path establishment and traffic packet routing in a layered communication network |
| |
Authors: | C S Sung S H Song |
| |
Affiliation: | 1.Department of Industrial Engineering,Korea Advanced Institute of Science and Technology,Taejon,Korea |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|