Alternate Second Order Conic Programming Reformulations for Hub Location with Capacity Selection under Demand

Sneha Dhyani, Sachin Jayaswal, Ankur Sinha and Navneet Vidyarthi

IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department

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.

Date: 2019-12-10
New Economics Papers: this item is included in nep-cmp, nep-ore and nep-tre
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.iima.ac.in/sites/default/files/rnpfiles/11779839142018-12-04.pdf English Version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:iim:iimawp:14617

Access Statistics for this paper

More papers in IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department Contact information at EDIRC.
Bibliographic data for series maintained by ().