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
Dans cet article, nous considérons conjointement les problèmes de routage des VP de travail et des VP de secours et utilisons l'approche basée sur la programmation entière pour maximiser l'utilisation des ressources du système et la capacité de survie du réseau. Le problème de planification VP est formulé comme un problème d’optimisation combinatoire non linéaire. La fonction objectif minimise l'utilisation des ressources tout en maximisant la capacité de survie du réseau. Par une transformation appropriée de la fonction objectif et l'application de la méthode du plan de coupe, la formulation originale est transformée en une formulation de programmation linéaire entière qui convient à l'application des techniques de relaxation lagrangienne. Après relaxation lagrangienne, le problème est ensuite décomposé en plusieurs sous-problèmes traitables. Contrairement aux travaux d'autres chercheurs, l'ensemble des chemins candidats n'a pas besoin d'être préparé à l'avance et les meilleurs chemins sont générés lors de la résolution des sous-problèmes de notre approche. Des algorithmes heuristiques basés sur la procédure de résolution de la relaxation lagrangienne sont développés. Un examen attentif de l'écart entre les limites supérieures heuristiques et les limites inférieures lagrangiennes révèle que l'algorithme proposé peut fournir efficacement une solution presque optimale pour la conception de la disposition VP survivante dans les réseaux ATM.
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.
Copier
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
Copier
@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},}
Copier
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 -