Regenerator location problem: Polyhedral study and effective branch-and-cut algorithms

In this paper, we study the regenerator location problem (RLP). This problem arises in optical networks where an optical signal can only travel a certain maximum distance (called the optical reach) before its quality deteriorates, needing regenerations by regenerators deployed at network nodes. The RLP is to determine a minimal number of network nodes for regenerator placement, such that for each node pair, there exists a path of which no sub-path without internal regenerators has a length greater than the optical reach. Starting with a set covering formulation involving an exponential number of constraints, reported and studied in Rahman (2012) and Aneja (2012), we study the facial structure of the polytope arising from this formulation, significantly extending known results. Making use of these polyhedral results, we present a new branch-and-cut (B&C) solution approach to solve the RLP to optimality. We present a series of computational experiments to evaluate two versions of the proposed B&C approach. Over 400 benchmark RLP instances, we first compare them with an available exact method for the RLP in the literature. Because of the equivalence among the RLP, the minimum connected dominating set problem (MCDSP), and the maximum leaf spanning tree problem (MLSTP), we further compare our approaches with other available exact algorithms using 47 benchmark MCDSP/MLSTP instances.