Exact method for the capacitated competitive facility location problem

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.