Alternate second order conic programming reformulations for hub location with capacity selection under demand uncertainty
View/ Open
Date
2018Author
Dhyani, Sneha
Jayaswal, Sachin
Sinha, Ankur
Vidyarthi, Navneet
Metadata
Show full item recordAbstract
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) 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.
Collections
- Working Papers [2627]