Design of widearea communication networks with backup path restoration using path generation technique
(2003) 4th International Workshop on the Design of Reliable Commuication Networks DRCN 2007 In Proceedings. 4th International Workshop on the Design of Reliable Communication Networks (DRCN 2003) p.7784 Abstract
 In this work, we study a flow restoration based network design problem where we assume the knowledge of possible failure situations. We use the idea of a situation disjoint path pair (nominal path, backup path) which are constructed in such a way that at least one of them is operational in any given failure situation for a flow. We present an approximate linear programming formulation of the problem and show how path generation technique (based on column generation) can be used to solve it. The path generation approach is an iterative method that allows us to add new path pairs based on dual Lagrangean multipliers in every iteration. We consider four different scenarios that differ in the way we compute and add new path pairs at every... (More)
 In this work, we study a flow restoration based network design problem where we assume the knowledge of possible failure situations. We use the idea of a situation disjoint path pair (nominal path, backup path) which are constructed in such a way that at least one of them is operational in any given failure situation for a flow. We present an approximate linear programming formulation of the problem and show how path generation technique (based on column generation) can be used to solve it. The path generation approach is an iterative method that allows us to add new path pairs based on dual Lagrangean multipliers in every iteration. We consider four different scenarios that differ in the way we compute and add new path pairs at every iteration. We present the results of our approach for an example network. From our observations, we conclude that path generation approach is an effective method to solve the backup path restoration design problem. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/1024494
 author
 Krithikaivasan, Bala; Srivastava, Shekhar; Pioro, Michal ^{LU} and Medhi, Deep
 organization
 publishing date
 2003
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 linear programming, telecommunication network routing, iterative methods
 in
 Proceedings. 4th International Workshop on the Design of Reliable Communication Networks (DRCN 2003)
 pages
 8 pages
 publisher
 IEEEInstitute of Electrical and Electronics Engineers Inc.
 conference name
 4th International Workshop on the Design of Reliable Commuication Networks DRCN 2007
 external identifiers

 Scopus:84945957283
 ISBN
 0780381181
 DOI
 10.1109/DRCN.2003.1275341
 language
 English
 LU publication?
 yes
 id
 b43657c0bf3140558b6aca8617c1a61e (old id 1024494)
 date added to LUP
 20080205 13:56:21
 date last changed
 20161013 04:43:20
@misc{b43657c0bf3140558b6aca8617c1a61e, abstract = {In this work, we study a flow restoration based network design problem where we assume the knowledge of possible failure situations. We use the idea of a situation disjoint path pair (nominal path, backup path) which are constructed in such a way that at least one of them is operational in any given failure situation for a flow. We present an approximate linear programming formulation of the problem and show how path generation technique (based on column generation) can be used to solve it. The path generation approach is an iterative method that allows us to add new path pairs based on dual Lagrangean multipliers in every iteration. We consider four different scenarios that differ in the way we compute and add new path pairs at every iteration. We present the results of our approach for an example network. From our observations, we conclude that path generation approach is an effective method to solve the backup path restoration design problem.}, author = {Krithikaivasan, Bala and Srivastava, Shekhar and Pioro, Michal and Medhi, Deep}, isbn = {0780381181}, keyword = {linear programming,telecommunication network routing,iterative methods}, language = {eng}, pages = {7784}, publisher = {ARRAY(0x8e37a80)}, series = {Proceedings. 4th International Workshop on the Design of Reliable Communication Networks (DRCN 2003)}, title = {Design of widearea communication networks with backup path restoration using path generation technique}, url = {http://dx.doi.org/10.1109/DRCN.2003.1275341}, year = {2003}, }