Abstract: We consider a model, called the CompFLP, that describes a decision-making process arising in the competitive location, where two parties open their facilities with the aim to capture customers and optimize own objective functions. The process is assumed to be organized in a Stackelberg game framework, where one of the parties open its facilities first, and the second party makes its decision when knowing the competitor’s one. Each customer follows a binary behavior rule and patronizes a single facility which is the most preferable for him or her. The parties’ objective functions are similar to those used in the classical facility location problem and represent the profit value computed as the income from serving the customers minus fixed cost of open facilities. The model is formalized as a pessimistic bilevel program. Based on its relaxation, called a high-point problem, which is a single-level MIP obtained by removing a restriction on the lower-level variables to take their optimal values, we construct a series of strengthened estimating problems (SEP) approximating the initial bilevel one. Each consequent SEP is obtained from the previous one by adding a number of constraints that are shown to be satisfied by some optimal solution of the bilevel program Thus, each SEP provides a valid upper bound for the optimum of the model under consideration. The constraints are taken from two reach families, called c-cuts and f-cuts. C-cuts “simulate” a rational behavior of the second party and force the lower-level location variables to take non-zero values for some profitable facilities. F-cuts utilize the idea to decompose the lower-level problem into several independent subproblems and memorize their optimal solutions to inherit them where it is possible. The computation process aiming to find an optimal solution of the bilevel problem is organized as a cut generation procedure where c-cuts are generated on-the-fly and are introduced into the model by a callback provided to a MIP solver. F-cuts need a bilevel feasible solution to be computed and supplement the model after the lower bound computation. In the numerical experiments with artificially generated data, we evaluate the performance of the scheme and compare it with previously suggested methods. We show that Instances of a relative problem, called Competitive prioritized set covering problem, which was previously solved in an optimistic formulation only, can be tackled by the scheme as well.

Cite: Melʹnikov A.A. , Beresnev V.L.
Cut generation scheme for the competitive facility location problem
International Conference on Operations Research (OR-2018) 08-12 Sep 2018