Formulations and Approximation Algorithms for Multilevel Uncapacitated Facility Location

Camilo Ortiz-Astorquiza (), Ivan Contreras () and Gilbert Laporte ()
Additional contact information
Camilo Ortiz-Astorquiza: Concordia University and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montreal, Canada H3G 1M8
Ivan Contreras: Concordia University and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montreal, Canada H3G 1M8
Gilbert Laporte: HEC Montréal and Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montreal, Canada H3T 2A7

INFORMS Journal on Computing, 2017, vol. 29, issue 4, 767-779

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 derive worst-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.

Keywords: multilevel facility location; submodularity; greedy heuristic (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2017.0757 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:29:y:2017:i:4:p:767-779

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().