Exact method for the capacitated competitive facility location problem

We consider a competition between two parties maximizing their profit from servicing customers. A decision making process is assumed to be organized in a Stackelberg game framework. In the model, we are given with two finite sets: a set of customers and a set of potential facilities’ locations. The parties, called the Leader and the Follower, sequentially open their facilities in some of the potential locations. A party opening the most preferable facility for a customer captures him or her. Facilities’ capacities are assumed to be finite, and the problem is to decide where to open facilities and how to assign them to service captured customers provided that capacity constraints are satisfied. The Leader's problem is formalized as an optimistic bi-level mixed-integer program. We show that it can be considered as a problem to maximize a pseudo-Boolean function depending on a “small” number of Boolean variables. To find an optimal solution of this problem, we suggest a branch-and-bound algorithm where an estimating problem in a form of mixed-integer programming is utilized to calculate an upper bound for values of the objective function. In computational experiments, we study the quality of the upper bound and the performance of the method on randomly generated inputs.