Branch, Bound & Cut Algorithm for the Competitive Facility Location Problem with Income Targeting

We consider a competitive facility location model with uncertain customers’ parameters. The model is built on the base of a Stackelberg game framework where competing parties (the Leader and the Follower) sequentially decide on opening their facilities. In the model, the Leader does not have a full information regarding the set of customers and considers a relatively small set of scenarios for this set’s realizations. The Leader minimizes its losses represented by fixed costs of open facilities and value of a shortage computed with respect to predefined target income values set for the scenarios. To find the Leader’s pessimistic optimal solution, we suggest an implicit enumeration algorithm, where a cut generation procedure is employed to compute bounds for the objective function. The procedure consists in iterative solving of estimating optimization problems, derived from a high-point relaxation of an initial bi-level model. On each iteration, an auxiliary optimization problem is solved to generate additional cuts, tightening the bound. This problem aims to find the strongest cuts in a rich family called c-cuts. In numerical experiments with synthetic data, we investigate a behavior of the model’s solution and an efficiency of the algorithm’s ingredients