EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

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:00
Room: 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

Status: accepted


Back to the list of papers