Xiangyong Li* , Y. P. Aneja

European Journal of Operational Research 257(2017)

Recommended reason

This paper studies the regenerator location problem (RLP) in optical networks. Starting with a set covering formulation involving an exponential number of constraints, reported and studied in Rahman (2012) and Aneja (2012), authors study the facial structure of the polytope arising from this formulation, significantly extending known results. Making use of these polyhedral results, they present a new branch-and-cut (B&C) solution approach to solve the RLP to optimality

About the author

Xiangyong Li: School of Economics and Management, Tongji University. professor.
Y. P. Aneja: Odette School of Business, University of Windsor

Keywords

Optical network design, Regenerator placement, Integer programming, Branch and cut, Facets

Brief introduction

Regenerator location problem (RLP) 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

In this paper, we study the associated polyhedral structure, starting with a set covering formulation, and develop new efficient branch-and-cut approaches. We study the polyhedral structure of the polytope of the convex hull of all feasible solutions, including: (1) derive necessary and sufficient conditions under which our constraints are facet defining, (2) provide a method to lift non-facet-defining inequalities to get stronger “lifted inequalities”, (3) present necessary and sufficient conditions under which these lifted inequalities are facet defining, and (4) give an approach to lift these non-facet-defining lifted inequalities. Our first main result provides simple necessary and sufficient conditions for a set covering inequality to be a facet-defining inequality. Our conditions lead to an efficient method to test if a valid inequality obtained through the separation routine is facet-defining, and lifting it to one or a set of stronger inequalities if it is not facet-defining. With the proposed polyhedral results, we propose two versions of our B&C approach to solve the RLP to optimality: one using derived valid inequalities without lifting, and another using lifted inequalities. A series of experiments are finally carried out to evaluate the performance of the two versions of our B&C approach by comparing them with existing algorithms in the literature. Using 400 benchmark RLP in- stances, we first compare our approach with the one used in Chen et al. (2010). Because the RLP is equivalent to the MCDSP and the MLSTP, we then compare our approach with nine other exact algorithms using 47 benchmark MCDSP/MLSTP instances. The computational results demonstrate that our proposed approach outperforms other existing algorithms, especially for larger instances. The proposed approach extends our ability to solve large RLP instances with up to 500 nodes. Additionally, our computational results also demonstrate that our B&C approach does benefit from lifted cuts, resulting in a significant saving of running time.