A multicut outer-approximation approach for competitive facility location under random utilities
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...
Saved in:
Main Authors: | , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2020
|
Subjects: | |
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 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-6286 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-62862020-09-09T04:56:33Z A multicut outer-approximation approach for competitive facility location under random utilities MAI, Tien LODI, Andrea 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. 2020-08-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/5283 info:doi/10.1016/j.ejor.2020.01.020 https://ink.library.smu.edu.sg/context/sis_research/article/6286/viewcontent/1_s2.0_S0377221720300412_main.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Facilities planning and design Maximum capture Multinomial logit Mixed multinomial logit Multicut outer-approximation Artificial Intelligence and Robotics OS and Networks |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Facilities planning and design Maximum capture Multinomial logit Mixed multinomial logit Multicut outer-approximation Artificial Intelligence and Robotics OS and Networks |
spellingShingle |
Facilities planning and design Maximum capture Multinomial logit Mixed multinomial logit Multicut outer-approximation Artificial Intelligence and Robotics OS and Networks MAI, Tien LODI, Andrea A multicut outer-approximation approach for competitive facility location under random utilities |
description |
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. |
format |
text |
author |
MAI, Tien LODI, Andrea |
author_facet |
MAI, Tien LODI, Andrea |
author_sort |
MAI, Tien |
title |
A multicut outer-approximation approach for competitive facility location under random utilities |
title_short |
A multicut outer-approximation approach for competitive facility location under random utilities |
title_full |
A multicut outer-approximation approach for competitive facility location under random utilities |
title_fullStr |
A multicut outer-approximation approach for competitive facility location under random utilities |
title_full_unstemmed |
A multicut outer-approximation approach for competitive facility location under random utilities |
title_sort |
multicut outer-approximation approach for competitive facility location under random utilities |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2020 |
url |
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 |
_version_ |
1770575370310909952 |