Approximation of the competitive facility location problem with MIPs

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

We investigate a bi-level optimization program that models a two parties’ competition in the form of a Stackelberg game. Each of the parties must decide where to open facilities and how to assign them to service customers in a way that maximizes a profit. A party can service a customer only by a facility which is preferable to all the competitor's ones for that customer. In the present work, we introduce an exponential family of inequalities satisfied by all the feasible solutions of the bi-level model and show some properties of these inequalities. Based on these results, we develop a cut generation scheme that finds an optimal solution of the model by iteratively supplementing the relaxation of the model, called a high-point problem, with additional constraints. Further, we implement a branch-and-bound algorithm where the introduced constraints improve the upper bound's quality. In the experimental part of the paper, we tune the parameters of the algorithms and investigate their performance on artificially generated input data.

Original languageEnglish
Pages (from-to)139-148
Number of pages10
JournalComputers and Operations Research
Volume104
DOIs
Publication statusPublished - 1 Apr 2019

Keywords

  • Bi-level programming
  • Branch-and-bound.
  • Cut generation
  • Location
  • Stackelberg game
  • Branch-and-bound
  • CHOICE

Fingerprint Dive into the research topics of 'Approximation of the competitive facility location problem with MIPs'. Together they form a unique fingerprint.

Cite this