Back to Search
Start Over
A polyhedral study of a relaxation of the routing and spectrum allocation problem (Brief Announcement).
- Source :
- Procedia Computer Science; 2023, Vol. 223, p391-393, 3p
- Publication Year :
- 2023
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 18770509
- Volume :
- 223
- Database :
- Supplemental Index
- Journal :
- Procedia Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 172024808
- Full Text :
- https://doi.org/10.1016/j.procs.2023.08.257