Paper Info
Title
Dual-Based Local Search for the Connected Facility Location and Related Problems
Abstract
The connected facility location (ConFL) problem arises in a number of applications that relate to the design of telecommunication networks as well as data distribution and management problems on networks. It combines features of the uncapacitated facility location problem with the Steiner tree problem and is known to be NP-complete. In this setting, we wish to install a set of facilities on a communication network and assign customers to the installed facilities. In addition, the set of selected facilities needs to be connected by a Steiner tree. In this paper, we propose a dual-based local search heuristic that combines dual ascent and local search, which together yield strong lower and upper bounds to the optimal solution. Our procedure is applied to a slightly more general version of the ConFL problem that embraces a family of four different problems---the Steiner tree-star problem, the general Steiner tree-star problem, the ConFL problem, and the rent-or-buy problem---that combine facility location decisions with connectivity requirements. Consequently, our solution methodology successfully applies to all of them. We discuss a wide range of computational experiments that indicate that our heuristic is a very effective procedure that finds high-quality solutions very rapidly.
Year
DOI
Venue
2010
10.1287/ijoc.1090.0375
INFORMS Journal on Computing
Keywords
Field
DocType
steiner tree-star problem,steiner tree,connected facility location,uncapacitated facility location problem,general steiner tree-star problem,different problem,related problems,steiner tree problem,management problem,rent-or-buy problem,confl problem,dual-based local search,data management,network design,facility location,local search
Mathematical optimization,Heuristic,Telecommunications network,Network planning and design,Steiner tree problem,Facility location problem,Local search (optimization),1-center problem,Data management,Mathematics
Journal
Volume
Issue
ISSN
22
4
1091-9856
Citations 
PageRank 
References 
19
0.78
20
Authors
2
Name
Order
Citations
PageRank
M. Gisela Bardossy1221.89
S. Raghavan221616.30