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

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.