{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:20Z","timestamp":1740144500124,"version":"3.37.3"},"reference-count":30,"publisher":"EDP Sciences","issue":"5","license":[{"start":{"date-parts":[[2019,10,8]],"date-time":"2019-10-08T00:00:00Z","timestamp":1570492800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2018,9,4]]},"published-print":{"date-parts":[[2019,11]]},"abstract":"<jats:p>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%.<\/jats:p>","DOI":"10.1051\/ro\/2018072","type":"journal-article","created":{"date-parts":[[2018,9,6]],"date-time":"2018-09-06T10:03:27Z","timestamp":1536228207000},"page":"1513-1528","source":"Crossref","is-referenced-by-count":0,"title":["On the problem of minimizing the cost with optical devices in Wavelength Division Multiplexing optical networks: complexity analysis, mathematical formulation and improved heuristics"],"prefix":"10.1051","volume":"53","author":[{"given":"Daniel","family":"Morais dos Reis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3065-3999","authenticated-orcid":false,"given":"Nat\u00e3","family":"Goulart","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6831-2006","authenticated-orcid":false,"given":"Thiago F.","family":"Noronha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S\u00e9rgio Ricardo","family":"de Souza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2019,10,8]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1023\/A:1015061802659","volume":"8","author":"Aiex","year":"2002","journal-title":"J. Heuristics"},{"key":"R2","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/s11590-006-0031-4","volume":"1","author":"Aiex","year":"2007","journal-title":"Optim. Lett."},{"key":"R3","unstructured":"Antonakopoulos S. and Zhang L., Heuristics for fiber installation in optical network optimization. In: Proceedings of 2007 IEEE Global Telecommunications Conference. Washington, USA (2007) 2342\u20132347."},{"key":"R4","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/j.disopt.2006.10.002","volume":"4","author":"Avella","year":"2007","journal-title":"Dis. Optim."},{"key":"R5","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1287\/ijoc.6.2.154","volume":"2","author":"Bean","year":"1994","journal-title":"ORSA J. Comput."},{"key":"R6","first-page":"177","volume":"81","author":"Bienstock","year":"1998","journal-title":"Math. Prog."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Bondy J.A. and Murty U.S.R., Graph Theory with Applications. Macmillan, London (1976).","DOI":"10.1007\/978-1-349-03521-2"},{"key":"R8","unstructured":"Choi J.S., Golmie N., Lapeyrere F., Mouveaux F. and Su D., 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\u20131115."},{"key":"R9","unstructured":"Cisco. Introduction to DWDM technology. Technical Report. Cisco Systems Inc., San Jose, CA (2001)."},{"key":"R10","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"R11","unstructured":"Dutta A., Dutta N., Fujiwara M. and Technologies W.D.M., Optical Networks. Elsevier, Amsterdam (2004)."},{"key":"R12","doi-asserted-by":"crossref","first-page":"1229","DOI":"10.1016\/j.dam.2008.04.022","volume":"157","author":"Frangioni","year":"2009","journal-title":"Dis. Appl. Math."},{"key":"R13","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1002\/net.20365","volume":"55","author":"Frota","year":"2010","journal-title":"Networks"},{"key":"R14","doi-asserted-by":"crossref","first-page":"2547","DOI":"10.1016\/j.cor.2005.07.028","volume":"33","author":"Galinier","year":"2006","journal-title":"Comput. Oper. Res."},{"key":"R15","unstructured":"Garey M.R. and Johnson D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA (1990)."},{"key":"R16","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1007\/s10732-010-9143-1","volume":"17","author":"Gon\u00e7alves","year":"2011","journal-title":"J. Heuristics"},{"key":"R17","unstructured":"Goulart N., Dias L.G.S., de Souza S.R. and Noronha T.F., Biased random-key genetic algorithm for fiber installation in optical network optimization. In: IEEE Congress on Evolutionary Computation, New Orleans (2011) 2267\u20132271."},{"key":"R18","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1287\/opre.48.3.461.12439","volume":"48","author":"Holmberg","year":"2000","journal-title":"Oper. Res."},{"key":"R19","unstructured":"Louren\u00e7o H.R., Martin O.C. and St\u00fctzle T., Iterated local search. In: Handbook of Metaheuristics, edited by Glover F., Kochenberger G. and Hillier F.S., 1st edition. Springer (2003) 320\u2013353."},{"key":"R20","unstructured":"Louren\u00e7o H.R., Martin O.C. and St\u00fctzle T., Iterated Local Search: Framework and Applications, 2nd edition. Springer US, Boston, MA (2010) 363\u2013397."},{"key":"R21","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/272991.272995","volume":"8","author":"Matsumoto","year":"1998","journal-title":"ACM Trans. Model. Comput. Simul."},{"key":"R22","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1007\/s10898-010-9608-7","volume":"50","author":"Noronha","year":"2011","journal-title":"J. Global Optim."},{"key":"R23","unstructured":"Noronha T.F., Resende M.G.C. and Ribeiro C.C., System for Routing and Wavelength Assignment in Wavelength Division Multiplexing Optical Networks (2014). US8693871B2."},{"key":"R24","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1016\/j.ejor.2004.09.007","volume":"171","author":"Noronha","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"R25","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1002\/net.20371","volume":"55","author":"Orlowski","year":"2010","journal-title":"Networks"},{"key":"R26","doi-asserted-by":"crossref","first-page":"410","DOI":"10.4153\/CJM-1960-035-0","volume":"12","author":"Read","year":"1960","journal-title":"Can. J. Math."},{"key":"R27","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1007\/s10898-011-9769-z","volume":"54","author":"Ribeiro","year":"2012","journal-title":"J. Global Optim."},{"key":"R28","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1007\/s11590-014-0760-8","volume":"9","author":"Ribeiro","year":"2014","journal-title":"Optim. Lett."},{"key":"R29","unstructured":"Spears W. and De Jong K., On the virtues of parameterized uniform crossover. In: Proceedings of the Fourth International Conference on Genetic Algorithms. San Mateo, CA (1991) 230\u2013236."},{"key":"R30","first-page":"47","volume":"1","author":"Zang","year":"2000","journal-title":"Opt. Netw. Mag."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2018072\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T00:41:20Z","timestamp":1720572080000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2018072"}},"subtitle":[],"editor":[{"given":"Alain","family":"Quilliot","sequence":"first","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Rosa","family":"Figueiredo","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2019,10,8]]},"references-count":30,"journal-issue":{"issue":"5"},"alternative-id":["ro170264"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2018072","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"1290-3868"}],"subject":[],"published":{"date-parts":[[2019,10,8]]}}}