Author(s) :
A. Bley
,
S.M. Hashemi
,
M. Rezapour
The paper is published :
Electronic Notes in Discrete Mathematics
MSC 2000
- 90C10 Integer programming
Abstract :
We consider a generalized version of the rooted connected facility location problem which occurs in planning of telecommunication networks with both survivability and hop-length constraints. Given a set of client nodes, a set of potential facility nodes including one predetermined root facility, a set of optional Steiner nodes, and the set of the potential connections among these nodes, that task is to decide which facilities to open, how to assign the clients to the open facilities, and how to interconnect the open facilities in such a way, that the resulting network contains at least edge-disjoint paths, each containing at most H edges, between the root and each open facility and that the total cost for opening facilities and installing connections is minimal. We study two IP models for this problem and present a branch-and-cut algorithm based on Benders decomposition for nding its solution. Finally, we report computational results.
Keywords :
Connected facility location, survivability, integer programming