Outer approximation and submodular cuts for maximum capture facility location problems with random utilities

Ivana Ljubić, Eduardo Moreno

Research output: Contribution to journalArticlepeer-review

39 Scopus citations

Abstract

We consider a family of competitive facility location problems in which a “newcomer” company enters the market and has to decide where to locate a set of new facilities so as to maximize its market share. The multinomial logit model is used to estimate the captured customer demand. We propose a first branch-and-cut approach for this family of difficult mixed-integer non-linear problems. Our approach combines two types of cutting planes that exploit particular properties of the objective function: the first one are the outer-approximation cuts and the second one are the submodular cuts. The approach is computationally evaluated on three datasets from the recent literature. The obtained results show that our new branch-and-cut drastically outperforms state-of-the-art exact approaches, both in terms of the computing times, and in terms of the number of instances solved to optimality.

Original languageEnglish
Pages (from-to)46-56
Number of pages11
JournalEuropean Journal of Operational Research
Volume266
Issue number1
DOIs
StatePublished - 1 Apr 2018

Keywords

  • Branch-and-cut
  • Combinatorial optimization
  • Competitive facility location
  • Maximum capture
  • Random utility model

Fingerprint

Dive into the research topics of 'Outer approximation and submodular cuts for maximum capture facility location problems with random utilities'. Together they form a unique fingerprint.

Cite this