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.

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%.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2018072
Classification : 90C59
Mots-clés : Routing and Wavelength Assignment, optical network optimization, heuristics and metaheuristics, iterated local search
Morais dos Reis, Daniel 1 ; Goulart, Natã 1 ; Noronha, Thiago F. 1 ; de Souza, Sérgio Ricardo 1

1
@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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ro/2018072/

[1] R. Aiex, M.G.C. Resende and C.C. Ribeiro, Probability distribution of solution time in GRASP: an experimental investigation. J. Heuristics 8 (2002) 343–373. | DOI | Zbl

[2] R. Aiex, M.G.C. Resende and C.C. Ribeiro, TTT-plots: a perl program to create time-to-target plots. Optim. Lett. 1 (2007) 355–366. | DOI | MR | Zbl

[3] S. Antonakopoulos and L. Zhang, Heuristics for fiber installation in optical network optimization. In: Proceedings of 2007 IEEE Global Telecommunications Conference. Washington, USA (2007) 2342–2347.

[4] P. Avella, S. Mattia and A. Sassano, Metric inequalities and the network loading problem. Dis. Optim. 4 (2007) 103–114. | DOI | MR | Zbl

[5] J.C. Bean, Genetic algorithms and random keys for sequencing and optimization. ORSA J. Comput. 2 (1994) 154–160. | DOI | Zbl

[6] D. Bienstock, S. Chopra, O. Günlük and C. Tsai, Minimum cost capacity installation for multicommodity network flows. Math. Prog. 81 (1998) 177–199. | DOI | MR | Zbl

[7] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications. Macmillan, London (1976). | DOI | MR | Zbl

[8] J.S. Choi, N. Golmie, F. Lapeyrere, F. Mouveaux and D. Su, 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] E.W. Dijkstra, A note on two problems in connection with graphs. Numer. Math. 1 (1959) 269–271. | DOI | MR | Zbl

[11] A. Dutta, N. Dutta, M. Fujiwara and W.D.M. Technologies, Optical Networks. Elsevier, Amsterdam (2004).

[12] A. Frangioni and B. Gendron, 0–1 reformulations of the multicommodity capacitated network design problem. Dis. Appl. Math. 157 (2009) 1229–1241. | DOI | MR | Zbl

[13] Y. Frota, N. Maculan, T.F. Noronha and C.C. Ribeiro, A branch-and-cut algorithm for partition coloring. Networks 55 (2010) 194–204. | DOI | MR | Zbl

[14] P. Galinier and A. Hertz, A survey of local search methods for graph coloring. Comput. Oper. Res. 33 (2006) 2547–2562. | DOI | MR | Zbl

[15] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA (1990). | Zbl

[16] J.F. Gonçalves and M.G.C. Resende, Biased random-key genetic algorithms for combinatorial optimization. J. Heuristics 17 (2011) 487–525. | DOI

[17] N. Goulart, L.G.S. Dias, S.R. De Souza and T.F. Noronha, Biased random-key genetic algorithm for fiber installation in optical network optimization. In: IEEE Congress on Evolutionary Computation, New Orleans (2011) 2267–2271.

[18] K. Holmberg and D. Yuan, A lagrangian heuristic based branch-and-bound approach for the capacitated network design problem. Oper. Res. 48 (2000) 461–481. | DOI | MR | Zbl

[19] H.R. Lourenço, O.C. Martin and T. Stützle, Iterated local search. In: Handbook of Metaheuristics, edited by F. Glover, G. Kochenberger and F.S. Hillier, 1st edition. Springer (2003) 320–353. | MR | Zbl

[20] H.R. Lourenço, O.C. Martin and T. Stützle, Iterated Local Search: Framework and Applications, 2nd edition. Springer US, Boston, MA (2010) 363–397.

[21] M. Matsumoto and T. Nishimura, Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8 (1998) 3–30. | DOI | Zbl

[22] T.F. Noronha, M.G.C. Resende and C.C. Ribeiro, A biased random-key genetic algorithm for routing and wavelength assignment. J. Global Optim. 50 (2011) 503–518. | DOI

[23] T.F. Noronha, M.G.C. Resende and C.C. Ribeiro, System for Routing and Wavelength Assignment in Wavelength Division Multiplexing Optical Networks (2014). US8693871B2.

[24] T.F. Noronha and C.C. Ribeiro, Routing and wavelength assignment by partition coloring. Eur. J. Oper. Res. 171 (2006) 797–810. | DOI | Zbl

[25] S. Orlowski, R. Wessäly, M. Pióro and A. Tomaszewski, Sndlib 1.0 – survivable network design library. Networks 55 (2010) 276–286. | DOI

[26] R. Read, The number of fc-colored graphs on labelled nodes. Can. J. Math. 12 (1960) 410–414. | DOI | MR | Zbl

[27] C.C. Ribeiro, I. Rosseti and R. Vallejos, Exploiting run time distributions to compare sequential and parallel stochastic local search algorithms. J. Global Optim. 54 (2012) 405–429. | DOI | MR | Zbl

[28] C.C. Ribeiro, I. Rosseti and R. Vallejos, 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] W. Spears and K. De Jong, On the virtues of parameterized uniform crossover. In: Proceedings of the Fourth International Conference on Genetic Algorithms. San Mateo, CA (1991) 230–236.

[30] H. Zang, J.P. Jue and B. Mukherjee, A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks. Opt. Netw. Mag. 1 (2000) 47–60.

Cité par Sources :