Approximation of the competitive facility location problem with MIPs

Результат исследования: Научные публикации в периодических изданияхстатья

1 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)139-148
Число страниц10
ЖурналComputers and Operations Research
Том104
DOI
СостояниеОпубликовано - 1 апр 2019

    Fingerprint

Цитировать