Please use this identifier to cite or link to this item:
Title: Alternate second order conic programming reformulations for hub location with capacity selection under demand uncertainty
Authors: Dhyani, Sneha
Jayaswal, Sachin
Sinha, Ankur
Vidyarthi, Navneet
Keywords: Hub-and-Spoke Network;Congestion;Capacity Selection;Stochastic Demand;Single Allocation;Second Order Conic Programming
Issue Date: 2018
Publisher: Indian Institute of Management Ahmedabad
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.
Appears in Collections:Working Papers

Files in This Item:
File Description SizeFormat 
WP_2018_12_04.pdfWP_2018_12_04511.98 kBAdobe PDFView/Open

Items in IIMA Institutional Repository are protected by copyright, with all rights reserved, unless otherwise indicated.