A new branch-and-cut approach for the generalized regenerator location problem
- PDF / 712,082 Bytes
- 27 Pages / 439.37 x 666.142 pts Page_size
- 3 Downloads / 175 Views
A new branch-and-cut approach for the generalized regenerator location problem Xiangyong Li1
· Y. P. Aneja2
© Springer Science+Business Media, LLC, part of Springer Nature 2020
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
1 Introduction As telecommunication networks face increasing bandwidth demand and diminishing fiber availability, telecommunication service providers are moving towards a crucial milestone in network evolution: the optical network (Colombo and Trubian 2014). Based on the emergence of the optical layer in transport networks, an optical network is able to provide higher capacity and reduce costs for new applications such as the internet, video and multimedia interaction,
B
Xiangyong Li [email protected] Y. P. Aneja [email protected]
1
School of Economics & Management, Tongji University, Shanghai 200092, China
2
Odette School of Business, University of Windsor, Windsor, ON N9B 3P4, Canada
123
Annals of Operations Research
and advanced digital services. An optical network is composed of fiber-optic cables that are the primary communication medium for converting data and transmitting data as light pulses between sender and receiver nodes. In the last decade, optical network design has attracted extensive attention of research works, including research on network architectures, control and management, protection and survivability (Borne et al. 2006; Chen et al. 2010). Regarding optical network design, the geographical extent of optical signal transmission is an important issue. Optical signals always undergo degradation as they are transmitted along a fiber. That is, an optical signal can travel a maximum distance before its quality degrades to a level that requires the sign
Data Loading...
