A new branch-and-cut approach for the generalized regenerator location problem

Xiangyong Li () and Y. P. Aneja ()
Additional contact information
Xiangyong Li: Tongji University
Y. P. Aneja: University of Windsor

Annals of Operations Research, 2020, vol. 295, issue 1, No 11, 229-255

Abstract: Abstract In optical networks, a signal can only travel a maximum distance (called optical reach) before its quality deteriorates, needing regenerations by installing regenerators at network nodes. Such an optical reach is an important property of a transmission system, which is a necessary ingredient for enabling optical bypass and thus significantly affects optical network design. In this paper, we study the generalized regenerator location problem (GRLP) where we are given a set S of candidate locations for regenerator placement and a set T of network nodes required to communicate with each other. The GRLP is to find a minimal number of network nodes for regenerator placement, such that for each node pair in T, there exists a path of which no subpath without internal regenerators has a length greater than the given optical reach. Starting with an existing set covering formulation of the problem, we first study the facial structure of the associated polytope. Making use of these polyhedral results, we then present a new branch-and-cut solution approach to solve the GRLP to optimality. With benchmark instances and newly generated instances, we finally evaluate our approach and compare it with an existing method. Computational results demonstrate efficacy of our approach.

Keywords: Location; Optical network design; Regenerator placement; Facets; Branch and cut (search for similar items in EconPapers)
Date: 2020
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/s10479-020-03721-6 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:annopr:v:295:y:2020:i:1:d:10.1007_s10479-020-03721-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-020-03721-6

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().