Lagrangian decompositions for the two-level FTTx network design problem

We consider the design of a passive optical telecommunication access network, where clients have to be connected to an intermediate level of distribution points (DPs) and further on to some central offices (COs) in a tree-like fashion. Each client demands a given number of fiber connections to its C...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Andreas Bley, Ivana Ljubić, Olaf Maurer
Formato:	article
Lenguaje:	EN
Publicado:	Elsevier 2013
Materias:	Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/c89c6d5c6f654a3ea25f69981f65c078
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:c89c6d5c6f654a3ea25f69981f65c078
record_format	dspace
spelling	oai:doaj.org-article:c89c6d5c6f654a3ea25f69981f65c0782021-12-02T05:00:37ZLagrangian decompositions for the two-level FTTx network design problem2192-440610.1007/s13675-013-0014-zhttps://doaj.org/article/c89c6d5c6f654a3ea25f69981f65c0782013-11-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000204https://doaj.org/toc/2192-4406We consider the design of a passive optical telecommunication access network, where clients have to be connected to an intermediate level of distribution points (DPs) and further on to some central offices (COs) in a tree-like fashion. Each client demands a given number of fiber connections to its CO. Passive optical splitters installed at the DPs allow k connections to share a single common fiber between the DP and the CO. We consider fixed charge costs for the use of an edge of the underlying street network, of a DP, and of a CO and variable costs for installing fibers along the street edges and for installing splitters at the DPs. We present two Lagrangian decomposition approaches that decompose the problem based on the network structure and on the cost structure, respectively. The subproblems are solved using mixed integer programming (MIP) techniques. We report computational results for realistic instances and compare the efficiency of the Lagrangian approaches to the solutions of an integrated MIP model.Andreas BleyIvana LjubićOlaf MaurerElsevierarticleApplied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 1, Iss 3, Pp 221-252 (2013)
institution	DOAJ
collection	DOAJ
language	EN
topic	Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Andreas Bley Ivana Ljubić Olaf Maurer Lagrangian decompositions for the two-level FTTx network design problem
description	We consider the design of a passive optical telecommunication access network, where clients have to be connected to an intermediate level of distribution points (DPs) and further on to some central offices (COs) in a tree-like fashion. Each client demands a given number of fiber connections to its CO. Passive optical splitters installed at the DPs allow k connections to share a single common fiber between the DP and the CO. We consider fixed charge costs for the use of an edge of the underlying street network, of a DP, and of a CO and variable costs for installing fibers along the street edges and for installing splitters at the DPs. We present two Lagrangian decomposition approaches that decompose the problem based on the network structure and on the cost structure, respectively. The subproblems are solved using mixed integer programming (MIP) techniques. We report computational results for realistic instances and compare the efficiency of the Lagrangian approaches to the solutions of an integrated MIP model.
format	article
author	Andreas Bley Ivana Ljubić Olaf Maurer
author_facet	Andreas Bley Ivana Ljubić Olaf Maurer
author_sort	Andreas Bley
title	Lagrangian decompositions for the two-level FTTx network design problem
title_short	Lagrangian decompositions for the two-level FTTx network design problem
title_full	Lagrangian decompositions for the two-level FTTx network design problem
title_fullStr	Lagrangian decompositions for the two-level FTTx network design problem
title_full_unstemmed	Lagrangian decompositions for the two-level FTTx network design problem
title_sort	lagrangian decompositions for the two-level fttx network design problem
publisher	Elsevier
publishDate	2013
url	https://doaj.org/article/c89c6d5c6f654a3ea25f69981f65c078
work_keys_str_mv	AT andreasbley lagrangiandecompositionsforthetwolevelfttxnetworkdesignproblem AT ivanaljubic lagrangiandecompositionsforthetwolevelfttxnetworkdesignproblem AT olafmaurer lagrangiandecompositionsforthetwolevelfttxnetworkdesignproblem
_version_	1718400852924825600

Lagrangian decompositions for the two-level FTTx network design problem

Ejemplares similares