A Branch, Bound, and Cuts Algorithm for the Dynamic Competitive Facility Location Problem

We consider a dynamic competitive facility location problem modeling an interaction oftwo competing parties (Leader and Follower) who place their facilities within a planning horizonsplit into several time periods. The Leader is assumed to open his/her facilities at the beginningof the planning horizon and does not change his/her decision later, while the Follower can modifyhis/her choice within each time period. We propose an algorithm that computes the best Leader’sdecision and is built on the base of the branch-and-bound computational scheme. To computeupper bounds, a special relaxation of the initial bilevel problem strengthened with additionalconstraints (cuts) is used. The paper describes the construction of these constraints while utilizingauxiliary optimization problems; this provides the strongest cuts. On an instance of a dynamiccompetitive facility location on a network with three vertices, we demonstrate that the model iscapable to take into account information regarding the changes of problem’s parameters alongthe time period. An implementation of the branch-and-bound algorithm shows a significantbenefit from using the cuts specially designed for dynamic competitive models: it improves theupper bound’s quality and reduces the number of nodes in the branching tree.