| Abstract |
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.
|