A multicut outer-approximation approach for competitive facility location under random utilities

• Main Authors: MAI, Tien, LODI, Andrea
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2020
• Subjects: Facilities planning and design; Maximum capture; Multinomial logit; Mixed multinomial logit; Multicut outer-approximation; Artificial Intelligence and Robotics; OS and Networks
• Online Access: https://ink.library.smu.edu.sg/sis_research/5283; https://ink.library.smu.edu.sg/context/sis_research/article/6286/viewcontent/1_s2.0_S0377221720300412_main.pdf
• Institution: Singapore Management University

This work concerns the maximum capture facility location problem with random utilities, i.e., the problem of seeking to locate new facilities in a competitive market such that the captured demand of users is maximized, assuming that each individual chooses among all available facilities according to a random utility maximization model. The main challenge lies in the nonlinearity of the objective function. Motivated by the convexity and separable structure of such an objective function, we propose an enhanced implementation of the outer approximation scheme. Our algorithm works in a cutting plane fashion and allows to separate the objective function into a number of sub-functions and create linear cuts for each sub-function at each outer-approximation iteration. We compare our approach with the state-of-the-art method and, for the first time in an extensive way, with other existing nonlinear solvers using three data sets from recent literature. Our experiments show the robustness of our approach, especially on large instances, in terms of both computing time and number instances solved to optimality.