The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
본 논문에서는 작업 VP와 백업 VP 라우팅 문제를 공동으로 고려하고 정수 프로그래밍 기반 접근 방식을 사용하여 시스템 자원 활용도와 네트워크 생존성을 극대화합니다. VP 계획 문제는 비선형 조합 최적화 문제로 공식화됩니다. 목적 함수는 네트워크 생존성을 최대화하면서 리소스 사용량을 최소화합니다. 목적함수를 적절히 변환하고 절단면법을 적용함으로써 원래의 공식은 라그랑지안 완화 기법을 적용하기에 적합한 정수 선형 계획법 공식으로 변환됩니다. 라그랑지안 완화 후에 문제는 여러 다루기 쉬운 하위 문제로 더 분해됩니다. 다른 사람의 작업과 달리 후보 경로 세트를 미리 준비할 필요가 없으며 우리 접근 방식의 하위 문제를 해결하면서 최상의 경로가 생성됩니다. 라그랑지안 완화의 해결 절차를 기반으로 하는 휴리스틱 알고리즘이 개발되었습니다. 휴리스틱 상한과 라그랑지 하한 사이의 간격을 면밀히 조사하면 제안된 알고리즘이 ATM 네트워크에서 생존 가능한 VP 레이아웃 설계를 위한 거의 최적의 솔루션을 효율적으로 제공할 수 있음을 알 수 있습니다.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Cheng-Shong WU, Shi-Wei LEE, "Modeling, Algorithms and Analysis of Survivable VP Planning in ATM Networks" in IEICE TRANSACTIONS on Communications,
vol. E82-B, no. 4, pp. 591-599, April 1999, doi: .
Abstract: In this paper, we consider the working VP and backup VP routing problems jointly and employ the integer programming based approach to maximize the system resource utilization and the network survivability. The VP planning problem is formulated as a nonlinear combinatorial optimization problem. The objective function minimizes the resource usage while maximizing the network survivability. By proper transformation of the objective function and applying cutting plane method, the original formulation is transformed into an integer linear programing formulation which is suitable for applying Lagrangian relaxation techniques. After Lagrangian relaxation, the problem is further decomposed into several tractable subproblems. Unlike others' work, the candidate path set does not need to be prepared in advance and the best paths are generated while solving subproblems in our approach. Heuristic algorithms based on the solving procedure of the Lagrangian relaxation are developed. Closely examining the gap between the heuristic upper bounds and the Lagrangian lower bounds reveals that the proposed algorithm can efficiently provide a nearly optimal solution for the survivable VP layout design in ATM networks.
URL: https://global.ieice.org/en_transactions/communications/10.1587/e82-b_4_591/_p
부
@ARTICLE{e82-b_4_591,
author={Cheng-Shong WU, Shi-Wei LEE, },
journal={IEICE TRANSACTIONS on Communications},
title={Modeling, Algorithms and Analysis of Survivable VP Planning in ATM Networks},
year={1999},
volume={E82-B},
number={4},
pages={591-599},
abstract={In this paper, we consider the working VP and backup VP routing problems jointly and employ the integer programming based approach to maximize the system resource utilization and the network survivability. The VP planning problem is formulated as a nonlinear combinatorial optimization problem. The objective function minimizes the resource usage while maximizing the network survivability. By proper transformation of the objective function and applying cutting plane method, the original formulation is transformed into an integer linear programing formulation which is suitable for applying Lagrangian relaxation techniques. After Lagrangian relaxation, the problem is further decomposed into several tractable subproblems. Unlike others' work, the candidate path set does not need to be prepared in advance and the best paths are generated while solving subproblems in our approach. Heuristic algorithms based on the solving procedure of the Lagrangian relaxation are developed. Closely examining the gap between the heuristic upper bounds and the Lagrangian lower bounds reveals that the proposed algorithm can efficiently provide a nearly optimal solution for the survivable VP layout design in ATM networks.},
keywords={},
doi={},
ISSN={},
month={April},}
부
TY - JOUR
TI - Modeling, Algorithms and Analysis of Survivable VP Planning in ATM Networks
T2 - IEICE TRANSACTIONS on Communications
SP - 591
EP - 599
AU - Cheng-Shong WU
AU - Shi-Wei LEE
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E82-B
IS - 4
JA - IEICE TRANSACTIONS on Communications
Y1 - April 1999
AB - In this paper, we consider the working VP and backup VP routing problems jointly and employ the integer programming based approach to maximize the system resource utilization and the network survivability. The VP planning problem is formulated as a nonlinear combinatorial optimization problem. The objective function minimizes the resource usage while maximizing the network survivability. By proper transformation of the objective function and applying cutting plane method, the original formulation is transformed into an integer linear programing formulation which is suitable for applying Lagrangian relaxation techniques. After Lagrangian relaxation, the problem is further decomposed into several tractable subproblems. Unlike others' work, the candidate path set does not need to be prepared in advance and the best paths are generated while solving subproblems in our approach. Heuristic algorithms based on the solving procedure of the Lagrangian relaxation are developed. Closely examining the gap between the heuristic upper bounds and the Lagrangian lower bounds reveals that the proposed algorithm can efficiently provide a nearly optimal solution for the survivable VP layout design in ATM networks.
ER -