A polyhedral study of a relaxation of the routing and spectrum allocation problem

The routing and spectrum allocation (RSA) problem arises in the context of flexible grid optical networks, and consists in routing a set of demands through a network while simultaneously assigning a bandwidth to each demand, subject to non-overlapping constraints. One of the most effective integer...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Marenco, Javier, Bertero, Federico, Kerivin, Herve, Wagler, Annegret
Formato: Artículo publishedVersion
Lenguaje:Inglés
Publicado: Procedia Computer Science 2023
Materias:
Routing and spectrum allocation
Integer programming
Facets
Separation
Acceso en línea:https://repositorio.utdt.edu/handle/20.500.13098/12233
https://doi.org/10.1016/j.procs.2023.08.257
Aporte de:
Repositorio Digital Universidad Torcuato Di Tella de Universidad Torcuato Di Tella
id I57-R163-20.500.13098-12233
record_format dspace
spelling I57-R163-20.500.13098-122332023-12-21T07:00:22Z A polyhedral study of a relaxation of the routing and spectrum allocation problem Marenco, Javier Bertero, Federico Kerivin, Herve Wagler, Annegret Routing and spectrum allocation Integer programming Facets Separation The routing and spectrum allocation (RSA) problem arises in the context of flexible grid optical networks, and consists in routing a set of demands through a network while simultaneously assigning a bandwidth to each demand, subject to non-overlapping constraints. One of the most effective integer programming formulations for RSA is the DR-AOV formulation, presented in a previous work. In this work we explore a relaxation of this formulation with a subset of variables from the original formulation, in order to identify valid inequalities that could be useful within a cutting-plane environment for tackling RSA. We present basic properties of this relaxed formulation, we identify several families of facet-inducing inequalities, and we show that they can be separated in polynomial time. 2023-12-20T18:03:49Z 2023-12-20T18:03:49Z 2023 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion https://repositorio.utdt.edu/handle/20.500.13098/12233 https://doi.org/10.1016/j.procs.2023.08.257 eng info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-nd/4.0/deed.es pp. 391–393 application/pdf application/pdf Procedia Computer Science Elsevier
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 Routing and spectrum allocation
Integer programming
Facets
Separation
spellingShingle Routing and spectrum allocation
Integer programming
Facets
Separation
Marenco, Javier
Bertero, Federico
Kerivin, Herve
Wagler, Annegret
A polyhedral study of a relaxation of the routing and spectrum allocation problem
topic_facet Routing and spectrum allocation
Integer programming
Facets
Separation
description The routing and spectrum allocation (RSA) problem arises in the context of flexible grid optical networks, and consists in routing a set of demands through a network while simultaneously assigning a bandwidth to each demand, subject to non-overlapping constraints. One of the most effective integer programming formulations for RSA is the DR-AOV formulation, presented in a previous work. In this work we explore a relaxation of this formulation with a subset of variables from the original formulation, in order to identify valid inequalities that could be useful within a cutting-plane environment for tackling RSA. We present basic properties of this relaxed formulation, we identify several families of facet-inducing inequalities, and we show that they can be separated in polynomial time.
format Artículo
publishedVersion
author Marenco, Javier
Bertero, Federico
Kerivin, Herve
Wagler, Annegret
author_facet Marenco, Javier
Bertero, Federico
Kerivin, Herve
Wagler, Annegret
author_sort Marenco, Javier
title A polyhedral study of a relaxation of the routing and spectrum allocation problem
title_short A polyhedral study of a relaxation of the routing and spectrum allocation problem
title_full A polyhedral study of a relaxation of the routing and spectrum allocation problem
title_fullStr A polyhedral study of a relaxation of the routing and spectrum allocation problem
title_full_unstemmed A polyhedral study of a relaxation of the routing and spectrum allocation problem
title_sort polyhedral study of a relaxation of the routing and spectrum allocation problem
publisher Procedia Computer Science
publishDate 2023
url https://repositorio.utdt.edu/handle/20.500.13098/12233
https://doi.org/10.1016/j.procs.2023.08.257
work_keys_str_mv AT marencojavier apolyhedralstudyofarelaxationoftheroutingandspectrumallocationproblem
AT berterofederico apolyhedralstudyofarelaxationoftheroutingandspectrumallocationproblem
AT kerivinherve apolyhedralstudyofarelaxationoftheroutingandspectrumallocationproblem
AT waglerannegret apolyhedralstudyofarelaxationoftheroutingandspectrumallocationproblem
AT marencojavier polyhedralstudyofarelaxationoftheroutingandspectrumallocationproblem
AT berterofederico polyhedralstudyofarelaxationoftheroutingandspectrumallocationproblem
AT kerivinherve polyhedralstudyofarelaxationoftheroutingandspectrumallocationproblem
AT waglerannegret polyhedralstudyofarelaxationoftheroutingandspectrumallocationproblem
_version_ 1808040547182444544

Ejemplares similares