ILP Model and Relaxation-Based Decomposition Approach for Incremental Topology Optimization in p-Cycle Networks
p-cycle networks have attracted a considerable interest in the network survivability literature in recent years. However, most of the existing work assumes a known network topology upon which to apply p-cycle restoration. In the present work, we develop an incremental topology optimization ILP for p...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2012-01-01
|
| Series: | Journal of Computer Networks and Communications |
| Online Access: | http://dx.doi.org/10.1155/2012/546301 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849306573534396416 |
|---|---|
| author | Md. Noor-E-Alam Ahmed Zaky Kasem John Doucette |
| author_facet | Md. Noor-E-Alam Ahmed Zaky Kasem John Doucette |
| author_sort | Md. Noor-E-Alam |
| collection | DOAJ |
| description | p-cycle networks have attracted a considerable interest in the network survivability literature in recent years. However, most of the existing work assumes a known network topology upon which to apply p-cycle restoration. In the present work, we develop an incremental topology optimization ILP for p-cycle network design, where a known topology can be amended with new fibre links selected from a set of eligible spans. The ILP proves to be relatively easy to solve for small test case instances but becomes computationally intensive on larger networks. We then follow with a relaxation-based decomposition approach to overcome this challenge. The decomposition approach significantly reduces computational complexity of the problem, allowing the ILP to be solved in reasonable time with no statistically significant impact on solution optimality. |
| format | Article |
| id | doaj-art-370f55791cbd40c19f11cd5509789e63 |
| institution | Kabale University |
| issn | 2090-7141 2090-715X |
| language | English |
| publishDate | 2012-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Computer Networks and Communications |
| spelling | doaj-art-370f55791cbd40c19f11cd5509789e632025-08-20T03:55:02ZengWileyJournal of Computer Networks and Communications2090-71412090-715X2012-01-01201210.1155/2012/546301546301ILP Model and Relaxation-Based Decomposition Approach for Incremental Topology Optimization in p-Cycle NetworksMd. Noor-E-Alam0Ahmed Zaky Kasem1John Doucette2Department of Mechanical Engineering, University of Alberta, 4-9 Mechanical Engineering Building, Edmonton, AB, T6G 2G8, CanadaDepartment of Electrical and Computer Engineering, University of Alberta, Edmonton, AB, T6G 2V4, CanadaDepartment of Mechanical Engineering, University of Alberta, 4-9 Mechanical Engineering Building, Edmonton, AB, T6G 2G8, Canadap-cycle networks have attracted a considerable interest in the network survivability literature in recent years. However, most of the existing work assumes a known network topology upon which to apply p-cycle restoration. In the present work, we develop an incremental topology optimization ILP for p-cycle network design, where a known topology can be amended with new fibre links selected from a set of eligible spans. The ILP proves to be relatively easy to solve for small test case instances but becomes computationally intensive on larger networks. We then follow with a relaxation-based decomposition approach to overcome this challenge. The decomposition approach significantly reduces computational complexity of the problem, allowing the ILP to be solved in reasonable time with no statistically significant impact on solution optimality.http://dx.doi.org/10.1155/2012/546301 |
| spellingShingle | Md. Noor-E-Alam Ahmed Zaky Kasem John Doucette ILP Model and Relaxation-Based Decomposition Approach for Incremental Topology Optimization in p-Cycle Networks Journal of Computer Networks and Communications |
| title | ILP Model and Relaxation-Based Decomposition Approach for Incremental Topology Optimization in p-Cycle Networks |
| title_full | ILP Model and Relaxation-Based Decomposition Approach for Incremental Topology Optimization in p-Cycle Networks |
| title_fullStr | ILP Model and Relaxation-Based Decomposition Approach for Incremental Topology Optimization in p-Cycle Networks |
| title_full_unstemmed | ILP Model and Relaxation-Based Decomposition Approach for Incremental Topology Optimization in p-Cycle Networks |
| title_short | ILP Model and Relaxation-Based Decomposition Approach for Incremental Topology Optimization in p-Cycle Networks |
| title_sort | ilp model and relaxation based decomposition approach for incremental topology optimization in p cycle networks |
| url | http://dx.doi.org/10.1155/2012/546301 |
| work_keys_str_mv | AT mdnoorealam ilpmodelandrelaxationbaseddecompositionapproachforincrementaltopologyoptimizationinpcyclenetworks AT ahmedzakykasem ilpmodelandrelaxationbaseddecompositionapproachforincrementaltopologyoptimizationinpcyclenetworks AT johndoucette ilpmodelandrelaxationbaseddecompositionapproachforincrementaltopologyoptimizationinpcyclenetworks |