IP modeling of the survivable hop constrained connected facility location problem
Please always quote using this URN:urn:nbn:de:0296-matheon-12189
- 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.
Author: | Andreas Bley, S. M. Hashemi, Mohsen Rezapour |
---|---|
URN: | urn:nbn:de:0296-matheon-12189 |
Referee: | Martin Skutella |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2013/05/27 |
Release Date: | 2013/05/27 |
Tag: | connected facility location; integer programming; survivability |
Institute: | Research Center Matheon |
Technische Universität Berlin | |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C90 Applications of mathematical programming |
Preprint Number: | 1015 |