TY - JOUR

T1 - Approximation of the competitive facility location problem with MIPs

AU - Beresnev, Vladimir

AU - Melnikov, Andrey

PY - 2019/4/1

Y1 - 2019/4/1

N2 - 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.

AB - 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.

KW - Bi-level programming

KW - Branch-and-bound.

KW - Cut generation

KW - Location

KW - Stackelberg game

KW - Branch-and-bound

KW - CHOICE

UR - http://www.scopus.com/inward/record.url?scp=85058616958&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2018.12.010

DO - 10.1016/j.cor.2018.12.010

M3 - Article

AN - SCOPUS:85058616958

VL - 104

SP - 139

EP - 148

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

ER -