TY - GEN
T1 - Solving the static design routing and wavelength assignment problem
AU - Simonis, Helmut
PY - 2011
Y1 - 2011
N2 - In this paper we present a hybrid model for the static design variant of the routing and wavelength assignment problem in directed networks, an important benchmark problem in optical network design. Our solution uses a decomposition into a MIP model for the routing aspect, combined with a graph coloring step modelled using either MIP (Coin-OR), SAT (minisat) or finite domain constraints (ECLiPSe). We consider two possible objective functions, one minimizing the maximal number of frequencies used on any of the links, the other minimizing the total number of frequencies used. We compare the models on a set of benchmark tests, results show that the constraint model is much more scalable than the alternatives considered, and is the only one producing proven optimal or near optimal results when minimizing the total number of wavelengths.
AB - In this paper we present a hybrid model for the static design variant of the routing and wavelength assignment problem in directed networks, an important benchmark problem in optical network design. Our solution uses a decomposition into a MIP model for the routing aspect, combined with a graph coloring step modelled using either MIP (Coin-OR), SAT (minisat) or finite domain constraints (ECLiPSe). We consider two possible objective functions, one minimizing the maximal number of frequencies used on any of the links, the other minimizing the total number of frequencies used. We compare the models on a set of benchmark tests, results show that the constraint model is much more scalable than the alternatives considered, and is the only one producing proven optimal or near optimal results when minimizing the total number of wavelengths.
UR - https://www.scopus.com/pages/publications/79952905023
U2 - 10.1007/978-3-642-19486-3_4
DO - 10.1007/978-3-642-19486-3_4
M3 - Conference proceeding
AN - SCOPUS:79952905023
SN - 9783642194856
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 59
EP - 75
BT - Recent Advances in Constraints - 14th Annual ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2009, Revised Selected Papers
T2 - 14th Annual ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2009
Y2 - 15 June 2009 through 17 June 2009
ER -