Competitive Facility Location under Cross-Nested Logit Customer Choice Model: Hardness and Exact Approaches

We study the competitive facility location problem, where a firm aims to establish new facilities in a market already occupied by competitors. In this problem, customer behavior is crucial for making optimal location decisions. We explore a general class of customer choice models, known as the cross-nested logit (CNL) model, which is recognized for its flexibility and generality in predicting people's choice behavior. To explore the problem, we first demonstrate that it is NP-hard, even when there is only one customer class. We further show that this hardness result is tight, as the facility location problem under any simpler choice models (such as the logit or nested logit) is polynomial-time solvable when there is one customer class. To tackle the resulting facility location problem, we demonstrate that the objective function under a general cross-nested structure is not concave. Interestingly, we show that by a change of variables, the objective function can be converted to a convex program (i.e., a maximization problem with a concave objective and convex constraints), enabling it to be solved to optimality via an outer-approximation algorithm. Extensive experiments show the efficiency of our approach and provide analyses on the benefits of using the cross-nested model in the facility location context.