An outer approximation-Benders’ decomposition approach for the competitive facility location problem with limited choice rule

Abstract

Abstract In this study, we propose a new exact approach to the competitive facility location problem with a limited choice rule. The problem consists in locating facilities to capture a market share that maximizes the profits of a new company entering into a competitive marketplace, knowing that customers patronize a limited number of the nearest facilities, i.e., they have a limited choice of facilities to favor. We propose an outer approximation approach devised to handle the nonlinear nature of the problem, with its master problem being solved using a multicut-variant Benders’ decomposition algorithm. Given the designed decomposition structure of the outer approximation master problem, we can analytically separate Benders’ feasibility cuts for each customer at a time. Our outer approximation-Benders’ decomposition algorithm outperformed existing methods in the literature when solving medium- and large-scale instances, being, on average, seven and two times faster, respectively, than the fastest previously reported method.