Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 46-56 |
Number of pages | 11 |
Journal | European Journal of Operational Research |
Volume | 266 |
Issue number | 1 |
DOIs | |
State | Published - 1 Apr 2018 |
Keywords
- Branch-and-cut
- Combinatorial optimization
- Competitive facility location
- Maximum capture
- Random utility model