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

Amaro Sousa (), Carlos Borges Lopes () and Paulo Monteiro ()
Additional contact information
Amaro Sousa: Universidade de Aveiro
Carlos Borges Lopes: Instituto de Telecomunicações
Paulo Monteiro: Universidade de Aveiro

EURO Journal on Computational Optimization, 2016, vol. 4, issue 2, No 5, 189-213

Abstract: Abstract 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.

Keywords: Integer linear programming; Network design; RWA; OTN; Telecommunications; 90B10 Network models; deterministic; 90C35 Programming involving graphs or networks; 90C90 Applications of mathematical programming (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s13675-015-0043-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurjco:v:4:y:2016:i:2:d:10.1007_s13675-015-0043-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13675

DOI: 10.1007/s13675-015-0043-x

Access Statistics for this article

EURO Journal on Computational Optimization is currently edited by Martine C. Labbé

More articles in EURO Journal on Computational Optimization from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().