Abstract
This paper studies multilevel uncapacitated p-location problems, a general class of facility location problems. We use a combinatorial representation of the general problem where the objective function satisfies the submodular property, and we exploit this characterization to deriveworst-case bounds for a greedy heuristic.We also obtain sharper bounds when the setup cost for opening facilities is zero and the allocation profits are nonnegative. Moreover,we introduce a mixed integer linear programming formulation for the problem based on the submodularity property. We present results of computational experiments to assess the performance of the greedy heuristic and that of the formulation. We compare the models with previously studied formulations.
| Original language | English |
|---|---|
| Pages (from-to) | 767-779 |
| Number of pages | 13 |
| Journal | INFORMS Journal on Computing |
| Volume | 29 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - 1 Sept 2017 |
Funding
History: Accepted by Karen Aardal, Area Editor for Design and Analysis of Algorithms. Funding: This research was partly funded by the Canadian Natural Sciences and Engineering Research Council [Grants 418609-2012 and 2015-06189] and by the Fonds de Recherche du Québec—Nature et Technologies [Grant 2014-NC-172906]. SupplementalMaterial: The online supplement and data are available at https://doi.org/10.1287/ ijoc.2017.0757. The support of the Canadian Natural Sciences and Engineering Research Council and the Fonds de Recherche du Québec–Nature et Technologie is gratefully acknowledged. The authors thank two anonymous reviewers for their valuable comments on a previous version of the paper.
Keywords
- Greedy heuristic
- Multilevel facility location
- Submodularity
ASJC Scopus subject areas
- Software
- Information Systems
- Computer Science Applications
- Management Science and Operations Research