Multi-level facility location as the maximization of a submodular set function

Camilo Ortiz-Astorquiza, Ivan Contreras, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

14 Citations (SciVal)

Abstract

In this paper we model the multi-level uncapacitated facility location problem as two different combinatorial optimization problems. The first model is the classical representation of the problem which uses a set of vertices as combinatorial objects to represent solutions whereas in the second model we propose the use of a set of paths. An interesting observation is that the real-valued set function associated with the first combinatorial problem does not satisfy the submodular property, whereas the set function associated with the second problem does satisfy this property. This illustrates the fact that submodularity is not a property intrinsic to an optimization problem but rather to its mathematical representation.

Original languageEnglish
Article number13006
Pages (from-to)1013-1016
Number of pages4
JournalEuropean Journal of Operational Research
Volume247
Issue number3
DOIs
Publication statusPublished - 16 Dec 2015

Keywords

  • Multi-level facility location
  • Submodularity

ASJC Scopus subject areas

  • General Computer Science
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'Multi-level facility location as the maximization of a submodular set function'. Together they form a unique fingerprint.

Cite this