Full Title: A Model-Free Approach for Solving Choice-Based Competitive Facility Location Problems Using Simulation and Submodularity

Abstract: In this talk we focus on facility location problems in which a firm entering a market seeks to open a set of available locations so as to maximize its expected market share, assuming that customers choose the alternative that maximizes a random utility function. We introduce a novel deterministic equivalent reformulation of this probabilistic model and, extending the results of previous studies, show that its objective function is submodular under any random utility maximization model. This reformulation characterizes the demand based on a finite set of preference profiles. Estimating their prevalence through simulation generalizes a sample average approximation method from the literature and results in a maximum covering problem for which we develop a new branch-and-cut algorithm. The proposed method takes advantage of the submodularity of the objective value to replace the least influential preference profiles by an auxiliary variable that is bounded by submodular cuts. This set of profiles is selected by a knee detection method. We provide a theoretical analysis of our approach and show that its computational performance, the solution quality it provides, and the efficiency of the knee detection method it exploits are directly connected to the entropy of the preference profiles in the population. Computational experiments on existing and new benchmark sets indicate that our approach dominates the classical sample average approximation method on large instances, can outperform the best heuristic method from the literature under the multinomial logit model, and achieves state-of-the-art results under the mixed multinomial logit model.

Bio: Emma Frejinger is a professor in the Department of Computer Science and Operations Research at Université de Montréal where she holds a Canada Research Chair and an industrial chair funded by the Canadian National Railway Company. Her research is application-driven and focuses on innovative combinations of methodologies from machine learning and operations research to solve large-scale decision-making problems. Emma has extensive experience working with industry, particularly within the transportation sector, where she has led collaborative research projects. Since 2018, she also works as a scientific advisor for IVADO Labs developing AI solutions for the supply chain industry. Before joining Université de Montréal in 2013, Emma was a faculty member at KTH Royal Institute of Technology in Sweden. She holds a Ph.D. in mathematics from EPFL (Switzerland).

To continue receiving all AI4OPT seminar announcements, please sign up to the mailing list at: [ Ссылка ]

Videos of the past seminars can be seen on AI4OPT webpage at: [ Ссылка ]

свернуть