Branch-and-cut approach based on generalized benders decomposition for facility location with limited choice rule

This paper studies the exact solution approaches for a generalized competitive facility location problem. We consider a company that plans to introduce a service by opening a set of facilities. The objective is to maximize the profit taking into account the revenue and the fixed cost. It is assumed that when customers are offered with a set of open facilities, they first form the consideration set, i.e., the subset of open facilities that the customers are willing to patronize. They then split the buying power among the facilities in the set plus some outside option, according to Luce's choice axiom. The resulting location problem provides a generalized framework that covers many existing models in competitive facility location problems where customers follow either the proportional choice rule or the partially binary choice rule. As our main contribution, we propose a branch-and-cut algorithm based on the generalized Benders decomposition scheme (B&C-Benders), which projects out high-dimensional continuous variables in modeling the consideration set and only works on the projected decision space. Our extensive computational experiment shows that B&C-Benders outperforms state-of-the-art exact approaches, both in terms of the computational time, and in terms of the number of instances solved to optimality. In the special case where customers follow the partially binary choice rule, B&C-Benders turns out to be efficient for large-scale instances with thousands of customer zones and hundreds of facilities. (C) 2020 Elsevier B.V. All rights reserved.

Automated summary

This paper studies exact solution approaches for a generalized competitive facility location problem and proposes a branch-and-cut algorithm based on the generalized Benders decomposition scheme (B&C-Benders). Computational experiments show that B&C-Benders outperforms state-of-the-art exact approaches in terms of computational time and number of instances solved to optimality, especially for large-scale instances.