A Branch-And-Benders-Cut approach for the fault tolerant regenerator location problem. (March 2020)

• Record Type: Journal Article
• Authors: Li, Xiangyong; Aneja, Y.P.
• Is Part Of: Computers & operations research. Volume 115(2020)
• Publication Date: 2020-03
• Subjects: Integer programming -- Benders decomposition -- Branch-and-cut -- Regenerator placement -- Fault management; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2019.104847
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We study the fault tolerant survivable regenerator location problem. We propose a branch and Benders cut approach. Results demonstrate effectiveness of the proposed approach. Abstract: We study the fault tolerant regenerator location problem (FTRLP) in optical networks, where any single network link (optical fiber) might fail, and an optical signal can only travel a maximum distance (called the optical reach) before its quality deteriorates, needing regenerations by installing regenerators at network nodes. The FTRLP is to find a minimal number of nodes for regenerator deployment such that each pair of nodes can communicate with each other for each single-link fault (failure) scenario. To solve the FTRLP to optimality, we propose a branch-and-Benders-cut (BBC) approach. During the exploration of the branch-and-bound search tree, the algorithm adds combinatorial Benders cuts. Computational results are provided and demonstrate effectiveness of the BBC approach.