Abstract: We consider a competitive facility location problem in the presence of uncertainty represented by a finite number of possible demand scenarios. The problem is formulated as a bi-level model built on the base of a Stackelberg game and a classic facility location model formalizing the players' decision process. In the bi-level model, the first player (Leader) has two options to open a facility. We assume that a Leader's facility could be opened either before the actual demand scenario is revealed or after the revelation. A fixed cost associated with the facility opening is lower in the first case. Thus the fixed costs could be reduced by making a preliminary location decision on the first stage and adjusting it on the second one. We suggest a procedure to compute an upper bound for the Leader's profit value. The approach is based on using a family of auxiliary bi-level subproblems. Optimal solutions of the subproblems form a feasible solution of the initial problem. The upper bound is computed by applying a cut generation procedure to strengthen high-point relaxations of the subproblems.

Cite: Melʹnikov A.A. , Beresnev V.L.
Computing an upper bound in the two-stage competitive location model
International Conference Mathematical Optimization Theory and Operations Research Petrozavodsk, Karelia, Russia, July 2-6, 2022 02-08 Jul 2022