TY - JOUR
T1 - Outer approximation and submodular cuts for maximum capture facility location problems with random utilities
AU - Ljubić, Ivana
AU - Moreno, Eduardo
N1 - Publisher Copyright:
© 2017 Elsevier B.V.
PY - 2018/4/1
Y1 - 2018/4/1
N2 - We consider a family of competitive facility location problems in which a “newcomer” company enters the market and has to decide where to locate a set of new facilities so as to maximize its market share. The multinomial logit model is used to estimate the captured customer demand. We propose a first branch-and-cut approach for this family of difficult mixed-integer non-linear problems. Our approach combines two types of cutting planes that exploit particular properties of the objective function: the first one are the outer-approximation cuts and the second one are the submodular cuts. The approach is computationally evaluated on three datasets from the recent literature. The obtained results show that our new branch-and-cut drastically outperforms state-of-the-art exact approaches, both in terms of the computing times, and in terms of the number of instances solved to optimality.
AB - We consider a family of competitive facility location problems in which a “newcomer” company enters the market and has to decide where to locate a set of new facilities so as to maximize its market share. The multinomial logit model is used to estimate the captured customer demand. We propose a first branch-and-cut approach for this family of difficult mixed-integer non-linear problems. Our approach combines two types of cutting planes that exploit particular properties of the objective function: the first one are the outer-approximation cuts and the second one are the submodular cuts. The approach is computationally evaluated on three datasets from the recent literature. The obtained results show that our new branch-and-cut drastically outperforms state-of-the-art exact approaches, both in terms of the computing times, and in terms of the number of instances solved to optimality.
KW - Branch-and-cut
KW - Combinatorial optimization
KW - Competitive facility location
KW - Maximum capture
KW - Random utility model
UR - http://www.scopus.com/inward/record.url?scp=85031398760&partnerID=8YFLogxK
U2 - 10.1016/j.ejor.2017.09.023
DO - 10.1016/j.ejor.2017.09.023
M3 - Article
AN - SCOPUS:85031398760
SN - 0377-2217
VL - 266
SP - 46
EP - 56
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 1
ER -