Quilliot, Alain ; Figueiredo, Rosa (éd.)
The Fiber Installation Problem (FIP) in Wavelength Division Multiplexing (WDM) optical networks consists in routing a set of lightpaths (all-optical connections) such that the cost of the optical devices necessary to operate the network is minimized. Each of these devices is worth hundreds of thousands of dollars. In consequence, any improvement in the lightpath routing may save millions of dollars for the network operator. All the works in the literature for solving this problem are based on greedy heuristics and genetic algorithms. No information is known on how good are the solutions provided by these heuristics compared to the optimal solution. Besides, no proof that the problem is NP-Hard can be found. In this paper, we prove that FIP is NP-Hard and also present an Integer Linear Programming (ILP) formulation for the problem. In addition, we propose an implementation of the Iterated Local Search (ILS) metaheuristic to solve large instances of the problem. Computational experiments carried out on 21 realistic instances showed that the CPLEX solver running with our ILP formulation was able to solve 11 out of the 21 instances to optimality in less than two minutes. These results also showed that the ILS heuristic has an average optimality gap of 1% on the instances for which the optimal solution is known. For the other instances, the results showed that the proposed heuristic outperforms the best heuristic in the literature by 7%.
Accepté le :
DOI : 10.1051/ro/2018072
Mots-clés : Routing and Wavelength Assignment, optical network optimization, heuristics and metaheuristics, iterated local search
@article{RO_2019__53_5_1513_0,
author = {Morais dos Reis, Daniel and Goulart, Nat\~a and Noronha, Thiago F. and de Souza, S\'ergio Ricardo},
editor = {Quilliot, Alain and Figueiredo, Rosa},
title = {On the problem of minimizing the cost with optical devices in {Wavelength} {Division} {Multiplexing} optical networks: complexity analysis, mathematical formulation and improved heuristics},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {1513--1528},
publisher = {EDP-Sciences},
volume = {53},
number = {5},
year = {2019},
doi = {10.1051/ro/2018072},
mrnumber = {4016085},
zbl = {1430.90561},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ro/2018072/}
}
TY - JOUR AU - Morais dos Reis, Daniel AU - Goulart, Natã AU - Noronha, Thiago F. AU - de Souza, Sérgio Ricardo ED - Quilliot, Alain ED - Figueiredo, Rosa TI - On the problem of minimizing the cost with optical devices in Wavelength Division Multiplexing optical networks: complexity analysis, mathematical formulation and improved heuristics JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2019 SP - 1513 EP - 1528 VL - 53 IS - 5 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2018072/ DO - 10.1051/ro/2018072 LA - en ID - RO_2019__53_5_1513_0 ER -
%0 Journal Article %A Morais dos Reis, Daniel %A Goulart, Natã %A Noronha, Thiago F. %A de Souza, Sérgio Ricardo %E Quilliot, Alain %E Figueiredo, Rosa %T On the problem of minimizing the cost with optical devices in Wavelength Division Multiplexing optical networks: complexity analysis, mathematical formulation and improved heuristics %J RAIRO - Operations Research - Recherche Opérationnelle %D 2019 %P 1513-1528 %V 53 %N 5 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2018072/ %R 10.1051/ro/2018072 %G en %F RO_2019__53_5_1513_0
Morais dos Reis, Daniel; Goulart, Natã; Noronha, Thiago F.; de Souza, Sérgio Ricardo. On the problem of minimizing the cost with optical devices in Wavelength Division Multiplexing optical networks: complexity analysis, mathematical formulation and improved heuristics. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 5, pp. 1513-1528. doi : 10.1051/ro/2018072. http://archive.numdam.org/articles/10.1051/ro/2018072/
[1] , and , Probability distribution of solution time in GRASP: an experimental investigation. J. Heuristics 8 (2002) 343–373. | DOI | Zbl
[2] , and , TTT-plots: a perl program to create time-to-target plots. Optim. Lett. 1 (2007) 355–366. | DOI | MR | Zbl
[3] and , Heuristics for fiber installation in optical network optimization. In: Proceedings of 2007 IEEE Global Telecommunications Conference. Washington, USA (2007) 2342–2347.
[4] , and , Metric inequalities and the network loading problem. Dis. Optim. 4 (2007) 103–114. | DOI | MR | Zbl
[5] , Genetic algorithms and random keys for sequencing and optimization. ORSA J. Comput. 2 (1994) 154–160. | DOI | Zbl
[6] , , and , Minimum cost capacity installation for multicommodity network flows. Math. Prog. 81 (1998) 177–199. | DOI | MR | Zbl
[7] and , Graph Theory with Applications. Macmillan, London (1976). | DOI | MR | Zbl
[8] , , , and , A functional classification of routing and wavelength assignment schemes in DWDM networks: static case. In: Proceedings of the 7th International Conference on Optical Communication and Networks, Paris (2000) 1109–1115.
[9] Cisco. Introduction to DWDM technology. Technical Report. Cisco Systems Inc., San Jose, CA (2001).
[10] , A note on two problems in connection with graphs. Numer. Math. 1 (1959) 269–271. | DOI | MR | Zbl
[11] , , and , Optical Networks. Elsevier, Amsterdam (2004).
[12] and , 0–1 reformulations of the multicommodity capacitated network design problem. Dis. Appl. Math. 157 (2009) 1229–1241. | DOI | MR | Zbl
[13] , , and , A branch-and-cut algorithm for partition coloring. Networks 55 (2010) 194–204. | DOI | MR | Zbl
[14] and , A survey of local search methods for graph coloring. Comput. Oper. Res. 33 (2006) 2547–2562. | DOI | MR | Zbl
[15] and , Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA (1990). | Zbl
[16] and , Biased random-key genetic algorithms for combinatorial optimization. J. Heuristics 17 (2011) 487–525. | DOI
[17] , , and , Biased random-key genetic algorithm for fiber installation in optical network optimization. In: IEEE Congress on Evolutionary Computation, New Orleans (2011) 2267–2271.
[18] and , A lagrangian heuristic based branch-and-bound approach for the capacitated network design problem. Oper. Res. 48 (2000) 461–481. | DOI | MR | Zbl
[19] , and , Iterated local search. In: Handbook of Metaheuristics, edited by , and , 1st edition. Springer (2003) 320–353. | MR | Zbl
[20] , and , Iterated Local Search: Framework and Applications, 2nd edition. Springer US, Boston, MA (2010) 363–397.
[21] and , Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8 (1998) 3–30. | DOI | Zbl
[22] , and , A biased random-key genetic algorithm for routing and wavelength assignment. J. Global Optim. 50 (2011) 503–518. | DOI
[23] , and , System for Routing and Wavelength Assignment in Wavelength Division Multiplexing Optical Networks (2014). US8693871B2.
[24] and , Routing and wavelength assignment by partition coloring. Eur. J. Oper. Res. 171 (2006) 797–810. | DOI | Zbl
[25] , , and , Sndlib 1.0 – survivable network design library. Networks 55 (2010) 276–286. | DOI
[26] , The number of fc-colored graphs on labelled nodes. Can. J. Math. 12 (1960) 410–414. | DOI | MR | Zbl
[27] , and , Exploiting run time distributions to compare sequential and parallel stochastic local search algorithms. J. Global Optim. 54 (2012) 405–429. | DOI | MR | Zbl
[28] , and , TTTplots-compare: a perl program to compare time-to-target plots or general runtime distributions of randomized algorithms. Optim. Lett. 9 (2014) 601–614. | DOI | MR | Zbl
[29] and , On the virtues of parameterized uniform crossover. In: Proceedings of the Fourth International Conference on Genetic Algorithms. San Mateo, CA (1991) 230–236.
[30] , and , A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks. Opt. Netw. Mag. 1 (2000) 47–60.
Cité par Sources :
