Computation of an Upper Bound in the Two-Stage Bilevel Competitive Location Model

We consider a competitive facility location problem with uncertainty represented by a finite number of possible demand scenarios. The problem is stated as a bilevel model constructed on the basis of a Stackelberg game and the classical facility location model formalizing the players’ decision process. In the bilevel model, the first player (Leader) has two options to open a facility. We assume that the Leader’s facility can be opened either before the actual demand scenario is revealed or after such a revelation. The fixed costs associated with the facility opening are lower in the former case. Thus, the fixed costs can be reduced by making a preliminary location decision at the first stage and adjusting it at the second one.

We suggest a procedure for computing an upper bound for the Leader’s profit. The approach is based on using a family of auxiliary bilevel subproblems. The optimal solutions of the subproblems form a feasible solution of the original problem. The upper bound is computed by applying a c-cut generation procedure to strengthen high-point relaxations of the subproblems.