Name
Abstract | ||
|---|---|---|
In this article, we introduce the regenerator location problem (RLP), which deals with a constraint on the geographical extent of transmission in optical networks. Specifically, an optical signal can only travel a maximum distance of dmax before its quality deteriorates to the point that it must be regenerated by installing regenerators at nodes of the network. As the cost of a regenerator is high, we wish to deploy as few regenerators as possible in the network, while ensuring all nodes can communicate with each other. We show that the RLP is NP-Complete. We then devise three heuristics for the RLP. We show how to represent the RLP as a max leaf spanning tree problem (MLSTP) on a transformed graph. Using this fact, we model the RLP as a Steiner arborescence problem (SAP) with a unit degree constraint on the root node. We also devise a branch-and-cut procedure to the directed cut formulation for the SAP problem. In our computational results over 740 test instances, the heuristic procedures obtained the optimal solution in 454 instances, whereas the branch-and-cut procedure obtained the optimal solution in 536 instances. These results indicate the quality of the heuristic solutions are quite good, and the branch-and-cut approach is viable for the optimal solution of problems with up to 100 nodes. Our approaches are also directly applicable to the MLSTP indicating that both the heuristics and branch-and-cut approach are viable options for the MLSTP. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010 |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1002/net.v55:3 | Networks |
Keywords | Field | DocType |
regenerator location problem,branch-and-cut procedure,branch-and-cut approach,heuristic solution,complexity.,greedy,sap problem,heuristic procedure,steiner arborescence problem,optical network,optimal solution,maximum leaf spanning tree problem,optical network design,tree problem,heuristics,branch-and-cut,spanning tree,branch and cut | Graph,Heuristic,Combinatorics,Mathematical optimization,Branch and cut,Arborescence,Heuristics,Spanning tree,Regenerative heat exchanger,Mathematics | Journal |
Volume | Issue | ISSN |
55 | 3 | 0028-3045 |
Citations | PageRank | References |
25 | 1.63 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Si Chen | 1 | 31 | 2.14 |
| Ivana Ljubic | 2 | 519 | 45.04 |
| S. Raghavan | 3 | 216 | 16.30 |