Compact ILP formulations for the routing and wavelength assignment problem in the design of optical transport networks with regenerators

This paper addresses two variants of the routing and wavelength assignment problem arising in the context of optical transport networks. In both variants, we address the case where the physical coverage of the fiber network is such that regenerators, to be placed on intermediate nodes of the lightpa...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Amaro de Sousa, CarlosBorges Lopes, Paulo Monteiro
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2016
Materias:	90B10 Network models, deterministic 90C35 Programming involving graphs or networks 90C90 Applications of mathematical programming Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/530bfa8e1cb7467d8345f5e23a99c27f
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:530bfa8e1cb7467d8345f5e23a99c27f
record_format	dspace
spelling	oai:doaj.org-article:530bfa8e1cb7467d8345f5e23a99c27f2021-12-02T05:00:52ZCompact ILP formulations for the routing and wavelength assignment problem in the design of optical transport networks with regenerators2192-440610.1007/s13675-015-0043-xhttps://doaj.org/article/530bfa8e1cb7467d8345f5e23a99c27f2016-05-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000617https://doaj.org/toc/2192-4406This paper addresses two variants of the routing and wavelength assignment problem arising in the context of optical transport networks. In both variants, we address the case where the physical coverage of the fiber network is such that regenerators, to be placed on intermediate nodes of the lightpaths, have to be used to reach full connectivity between network nodes. In the first variant, we aim to minimize the solution cost given by the sum of the costs of all electrical–optical–electrical converter components. In the second variant, among all minimum cost solutions, we aim to optimize the network load balancing by minimizing the highest assigned wavelength. For each problem variant, we start by defining a basic integer linear programming compact formulation. Then, we improve each formulation using variable reformulation and variable elimination techniques. Finally, we present computational results showing that the reformulated formulations with variable elimination let us obtain provable optimal solutions for problem instances of relevant size within reasonable runtimes.Amaro de SousaCarlosBorges LopesPaulo MonteiroElsevierarticle90B10 Network models, deterministic90C35 Programming involving graphs or networks90C90 Applications of mathematical programmingApplied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 4, Iss 2, Pp 189-213 (2016)
institution	DOAJ
collection	DOAJ
language	EN
topic	90B10 Network models, deterministic 90C35 Programming involving graphs or networks 90C90 Applications of mathematical programming Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90B10 Network models, deterministic 90C35 Programming involving graphs or networks 90C90 Applications of mathematical programming Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Amaro de Sousa CarlosBorges Lopes Paulo Monteiro Compact ILP formulations for the routing and wavelength assignment problem in the design of optical transport networks with regenerators
description	This paper addresses two variants of the routing and wavelength assignment problem arising in the context of optical transport networks. In both variants, we address the case where the physical coverage of the fiber network is such that regenerators, to be placed on intermediate nodes of the lightpaths, have to be used to reach full connectivity between network nodes. In the first variant, we aim to minimize the solution cost given by the sum of the costs of all electrical–optical–electrical converter components. In the second variant, among all minimum cost solutions, we aim to optimize the network load balancing by minimizing the highest assigned wavelength. For each problem variant, we start by defining a basic integer linear programming compact formulation. Then, we improve each formulation using variable reformulation and variable elimination techniques. Finally, we present computational results showing that the reformulated formulations with variable elimination let us obtain provable optimal solutions for problem instances of relevant size within reasonable runtimes.
format	article
author	Amaro de Sousa CarlosBorges Lopes Paulo Monteiro
author_facet	Amaro de Sousa CarlosBorges Lopes Paulo Monteiro
author_sort	Amaro de Sousa
title	Compact ILP formulations for the routing and wavelength assignment problem in the design of optical transport networks with regenerators
title_short	Compact ILP formulations for the routing and wavelength assignment problem in the design of optical transport networks with regenerators
title_full	Compact ILP formulations for the routing and wavelength assignment problem in the design of optical transport networks with regenerators
title_fullStr	Compact ILP formulations for the routing and wavelength assignment problem in the design of optical transport networks with regenerators
title_full_unstemmed	Compact ILP formulations for the routing and wavelength assignment problem in the design of optical transport networks with regenerators
title_sort	compact ilp formulations for the routing and wavelength assignment problem in the design of optical transport networks with regenerators
publisher	Elsevier
publishDate	2016
url	https://doaj.org/article/530bfa8e1cb7467d8345f5e23a99c27f
work_keys_str_mv	AT amarodesousa compactilpformulationsfortheroutingandwavelengthassignmentprobleminthedesignofopticaltransportnetworkswithregenerators AT carlosborgeslopes compactilpformulationsfortheroutingandwavelengthassignmentprobleminthedesignofopticaltransportnetworkswithregenerators AT paulomonteiro compactilpformulationsfortheroutingandwavelengthassignmentprobleminthedesignofopticaltransportnetworkswithregenerators
_version_	1718400827967668224

Compact ILP formulations for the routing and wavelength assignment problem in the design of optical transport networks with regenerators

Ejemplares similares