IP modeling of the survivable hop constrained connected facility location problem

Source file is available as :   Portable Document Format (PDF)

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