Approximation of the competitive facility location problem with MIPs Full article
| Journal |
Computers and Operations Research
ISSN: 0305-0548 , E-ISSN: 1873-765X |
||||
|---|---|---|---|---|---|
| Output data | Year: 2019, Volume: 104, Pages: 139-148 Pages count : 10 DOI: 10.1016/j.cor.2018.12.010 | ||||
| Tags | Bi-level programming; Branch-and-bound.; Cut generation; Location; Stackelberg game | ||||
| Authors |
|
||||
| Affiliations |
|
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
Cite:
Beresnev V.
, Melnikov A.
Approximation of the competitive facility location problem with MIPs
Computers and Operations Research. 2019. V.104. P.139-148. DOI: 10.1016/j.cor.2018.12.010 WOS Scopus OpenAlex
Approximation of the competitive facility location problem with MIPs
Computers and Operations Research. 2019. V.104. P.139-148. DOI: 10.1016/j.cor.2018.12.010 WOS Scopus OpenAlex
Identifiers:
| Web of science: | WOS:000458344800011 |
| Scopus: | 2-s2.0-85058616958 |
| OpenAlex: | W2905554915 |