TY - GEN
T1 - A hybrid constraint model for the routing and wavelength assignment problem
AU - Simonis, Helmut
PY - 2009
Y1 - 2009
N2 - In this paper we present a hybrid model for the demand acceptance 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 and optimization aspect, combined with a finite domain constraint model for the wavelength assignment. If a solution to the constraint problem is found, it provides an optimal solution to the overall problem. If the constraint problem is infeasible, we use an extended explanation technique to find a good relaxation of the problem which leads to a near optimal solution. Extensive experiments show that proven optimality is achieved for more than 99.8% of all cases tested, while run-times are orders of magnitude smaller than the best known MIP solution.
AB - In this paper we present a hybrid model for the demand acceptance 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 and optimization aspect, combined with a finite domain constraint model for the wavelength assignment. If a solution to the constraint problem is found, it provides an optimal solution to the overall problem. If the constraint problem is infeasible, we use an extended explanation technique to find a good relaxation of the problem which leads to a near optimal solution. Extensive experiments show that proven optimality is achieved for more than 99.8% of all cases tested, while run-times are orders of magnitude smaller than the best known MIP solution.
UR - https://www.scopus.com/pages/publications/70350782089
U2 - 10.1007/978-3-642-04244-7_11
DO - 10.1007/978-3-642-04244-7_11
M3 - Conference proceeding
AN - SCOPUS:70350782089
SN - 3642042430
SN - 9783642042430
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 104
EP - 118
BT - Principles and Practice of Constraint Programming - CP 2009 - 15th International Conference, CP 2009, Proceedings
T2 - 15th International Conference on Principles and Practice of Constraint Programming, CP 2009
Y2 - 20 September 2009 through 24 September 2009
ER -