Hub Interdiction & Hub Protection problems: Model formulations & Exact Solution methods. (Revised)

Prasanna Ramamoorthy, Sachin Jayaswal, Ankur Sinha and Navneet Vidyarthi

No WP2016-10-01, IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department

Abstract: In this paper, we present computationally efficient formulations for the hub interdiction problem. The problem is to identify a set of r critical hubs from an existing set of p hubs that when interdicted, results in the greatest disruption cost for the hub-and-spoke network owner. To begin with, the problem is modeled as a bilevel mixed integer linear program. We explore two ways to reduce this bilevel program to single level by replacing the lower level problem with constraints obtained i) using KKT conditions and ii) by exploiting the structure of the problem. Reduction using KKT conditions is straightforward but computationally inefficient in this context. Exploiting the structure of the problem, we propose two alternate forms of closest assignment constraints and study their computational e ffectiveness while solving the problem. We also show the dominance relationship between our proposed closest assignment constraints and the only other version studied in the literature. Our computational results suggest that with one form of our proposed closest assignment constraint the resulting model is solved on an average seven times faster than the proposed one in literature. We further propose refinements to these alternate forms of closest assignment constraints which are computationally faster than their original constraints. We also solve the single level hub interdiction problem using a Benders' decomposition method to fully exploit the potential of our proposed closest assignment constraint. The computational efficiency gained using the closest assignment constraints, makes the trilevel protection problem tractable. We reduce the trilevel hub protection problem to a bilevel problem, and solve it using an Implicit enumeration + Benders' decomposition procedure.

Date: 2016-10-25
New Economics Papers: this item is included in 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/21028611162016-10-01.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:14552

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 (respub@iima.ac.in).