Regenerator location problem: Polyhedral study and effective branch-and-cut algorithms
| Autor: | Xiangyong Li, Yash P. Aneja |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
021103 operations research
Information Systems and Management General Computer Science Node (networking) 0211 other engineering and technologies 020206 networking & telecommunications Polytope 02 engineering and technology Management Science and Operations Research Industrial and Manufacturing Engineering Connected dominating set Set (abstract data type) Modeling and Simulation Path (graph theory) 0202 electrical engineering electronic engineering information engineering Benchmark (computing) Branch and cut Integer programming Algorithm Mathematics |
| Zdroj: | European Journal of Operational Research. 257:25-40 |
| ISSN: | 0377-2217 |
| DOI: | 10.1016/j.ejor.2016.07.032 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect