EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
2178. Solving LP Relaxations for Routing and Wavelength Assignment Problem with Partial Path Protection
Invited abstract in session WA-29: Advances in Optimization for Industrial Applications, stream Combinatorial Optimization.
Wednesday, 8:30-10:00Room: 157 (building: 208)
Authors (first author is the speaker)
1. | Zhou Xu
|
Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University | |
2. | Xianyan Yang
|
Hong Kong Polytechnic University | |
3. | Junyan Liu
|
Huawei Hong Kong Research Center | |
4. | Fan Zhang
|
Huawei Hong Kong Research Centre | |
5. | Fabo Sun
|
Huawei | |
6. | Feng Li
|
Huazhong University of Science and Technology |
Abstract
This paper studies a routing and wavelength assignment problem for an optical-fiber telecommunication network, known as the RWAP with partial path protection (RWAP-PPP). The existing literature lacks any studies on its relaxations. As a result, the quality of solutions to the RWAP-PPP cannot be properly measured, which is critical to telecommunication service providers in their bidding to customers, and in their determination of service improvements. We derive and compare various linear programming (LP) relaxations of the RWAP-PPP, from which we propose a novel LP relaxation that can be efficiently solved by a Benders decomposition algorithm to produce good lower bounds for the RWAP-PPP. Computational results show that the newly proposed LP relaxation can be solved efficiently, even for some large-scale practical networks of hundreds of nodes and thousands of requests.
Keywords
- Programming, Linear
- Telecommunications
- Network Design
Status: accepted
Back to the list of papers