Working Papers | 2016
Hub Interdiction & Hub Protection problems: Model formulations & Exact Solution methods. (Revised)
Prasanna Ramamoorthy, Sachin Jayaswal, Ankur Sinha, and Navneet Vidyarthi
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 effectiveness 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.
Read More
