Formulations and approximation algorithms for multilevel uncapacitated facility location

Camilo Ortiz-Astorquiza, Ivan Contreras, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

7 Citations (SciVal)


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 languageEnglish
Pages (from-to)767-779
Number of pages13
JournalINFORMS Journal on Computing
Issue number4
Publication statusPublished - 1 Sept 2017


  • Greedy heuristic
  • Multilevel facility location
  • Submodularity

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Formulations and approximation algorithms for multilevel uncapacitated facility location'. Together they form a unique fingerprint.

Cite this