A branch-and-cut algorithm for the routing and spectrum allocation problem

One of the most promising solutions to deal with huge data traffic demands in large communication networks is given by flexible optical networking, in particular the flexible grid (flexgrid) technology specified in the ITU-T standard G.694.1. In this specification, the frequency spectrum of an op...

Descripción completa

Detalles Bibliográficos
Autores principales: Marenco, Javier, Bianchetti, Marcelo
Formato: info:eu-repo/semantics/preprint submittedVersion
Lenguaje:Inglés
Publicado: Universidad Torcuato Di Tella 2023
Materias:
Integer programming
Valid inequalities
Networking
Optical fibers
Flex-grid
Acceso en línea:https://repositorio.utdt.edu/handle/20.500.13098/12150
Aporte de:
Repositorio Digital Universidad Torcuato Di Tella de Universidad Torcuato Di Tella
id I57-R163-20.500.13098-12150
record_format dspace
spelling I57-R163-20.500.13098-121502023-11-23T07:00:26Z A branch-and-cut algorithm for the routing and spectrum allocation problem Marenco, Javier Bianchetti, Marcelo Integer programming Valid inequalities Networking Optical fibers Flex-grid One of the most promising solutions to deal with huge data traffic demands in large communication networks is given by flexible optical networking, in particular the flexible grid (flexgrid) technology specified in the ITU-T standard G.694.1. In this specification, the frequency spectrum of an optical fiber link is divided into narrow frequency slots. Any sequence of consecutive slots can be used as a simple channel, and such a channel can be switched in the network nodes to create a lightpath. In this kind of networks, the problem of establishing lightpaths for a set of end-to-end demands that compete for spectrum resources is called the routing and spectrum allocation problem (RSA). Due to its relevance, RSA has been intensively studied in the last years. It has been shown to be NP-hard and different solution approaches have been proposed for this problem. In this paper we present several families of valid inequalities, valid equations, and optimality cuts for a natural integer programming formulation of RSA and, based on these results, we develop a branch-and-cut algorithm for this problem. Our computational experiments suggest that such an approach is effective at tackling this problem. 2023-11-22T16:17:33Z 2023-11-22T16:17:33Z 2023 info:eu-repo/semantics/preprint info:eu-repo/semantics/submittedVersion https://repositorio.utdt.edu/handle/20.500.13098/12150 eng info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-sa/2.5/ar/ 34 p. application/pdf application/pdf Universidad Torcuato Di Tella
institution Universidad Torcuato Di Tella
institution_str I-57
repository_str R-163
collection Repositorio Digital Universidad Torcuato Di Tella
language Inglés
orig_language_str_mv eng
topic Integer programming
Valid inequalities
Networking
Optical fibers
Flex-grid
spellingShingle Integer programming
Valid inequalities
Networking
Optical fibers
Flex-grid
Marenco, Javier
Bianchetti, Marcelo
A branch-and-cut algorithm for the routing and spectrum allocation problem
topic_facet Integer programming
Valid inequalities
Networking
Optical fibers
Flex-grid
description One of the most promising solutions to deal with huge data traffic demands in large communication networks is given by flexible optical networking, in particular the flexible grid (flexgrid) technology specified in the ITU-T standard G.694.1. In this specification, the frequency spectrum of an optical fiber link is divided into narrow frequency slots. Any sequence of consecutive slots can be used as a simple channel, and such a channel can be switched in the network nodes to create a lightpath. In this kind of networks, the problem of establishing lightpaths for a set of end-to-end demands that compete for spectrum resources is called the routing and spectrum allocation problem (RSA). Due to its relevance, RSA has been intensively studied in the last years. It has been shown to be NP-hard and different solution approaches have been proposed for this problem. In this paper we present several families of valid inequalities, valid equations, and optimality cuts for a natural integer programming formulation of RSA and, based on these results, we develop a branch-and-cut algorithm for this problem. Our computational experiments suggest that such an approach is effective at tackling this problem.
format info:eu-repo/semantics/preprint
submittedVersion
author Marenco, Javier
Bianchetti, Marcelo
author_facet Marenco, Javier
Bianchetti, Marcelo
author_sort Marenco, Javier
title A branch-and-cut algorithm for the routing and spectrum allocation problem
title_short A branch-and-cut algorithm for the routing and spectrum allocation problem
title_full A branch-and-cut algorithm for the routing and spectrum allocation problem
title_fullStr A branch-and-cut algorithm for the routing and spectrum allocation problem
title_full_unstemmed A branch-and-cut algorithm for the routing and spectrum allocation problem
title_sort branch-and-cut algorithm for the routing and spectrum allocation problem
publisher Universidad Torcuato Di Tella
publishDate 2023
url https://repositorio.utdt.edu/handle/20.500.13098/12150
work_keys_str_mv AT marencojavier abranchandcutalgorithmfortheroutingandspectrumallocationproblem
AT bianchettimarcelo abranchandcutalgorithmfortheroutingandspectrumallocationproblem
AT marencojavier branchandcutalgorithmfortheroutingandspectrumallocationproblem
AT bianchettimarcelo branchandcutalgorithmfortheroutingandspectrumallocationproblem
_version_ 1808040728857673728

Ejemplares similares