Computing an upper bound in the two-stage bi-level competitive location model

We consider a competitive facility location problem with 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 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. The fixed costs associated with the facility opening are 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.
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. Tab. 1, illustr. 1, bibliogr. 10.