Alternating heuristic and exact method for the leader-follower facility location and design problem

We study the following discrete facility location game. Two players, a leader and a follower, open facilities and compete to attract clients from a given market. Each player has a budget and maximizes own market share. Each client splits own demand probabilistically over all opened facilities by the gravity rule. The goal is to find the location and design of the leader facilities to maximize his market share. We present an alternating heuristic and exact method for this game. We rewrite the problem as mixed integer linear program with exponential number of constraints. In our method, we start with small subset of constraints and iteratively enlarge it until upper and lower bounds not coincide. Computational results are discussed.