Alternate second order conic program reformulations for hub location under stochastic demand and congestion
| Autor: | Sachin Jayaswal, Navneet Vidyarthi, Sneha Dhyani Bhatt, Ankur Sinha |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Mathematical optimization
021103 operations research Computer science 0211 other engineering and technologies General Decision Sciences 02 engineering and technology Hub location problem Management Science and Operations Research Order (exchange) Conic section Theory of computation Spoke-hub distribution paradigm Selection (genetic algorithm) Integer (computer science) Curse of dimensionality |
| Zdroj: | Annals of Operations Research. 304:481-527 |
| ISSN: | 1572-9338 0254-5330 |
| Popis: | In this paper, we study the single allocation hub location problem with capacity selection in the presence of congestion at hubs. Accounting for congestion at hubs leads to a non-linear mixed integer program, for which we propose 18 alternate mixed integer second order conic program (MISOCP) based reformulations. Based on our computational studies, we identify the best MISOCP-based reformulation, which turns out to be 20–60 times faster than the state-of-the-art. Using the best MISOCP-based reformulation, we are able to exactly solve instances up to 50 nodes in less than half-an-hour. We also theoretically examine the dimensionality of the second order cones associated with different formulations, based on which their computational performances can be predicted. Our computational results corroborate our theoretical findings. Such insights can be helpful in the generation of efficient MISOCPs for similar classes of problems. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|