| dc.description.abstract | In this paper, we present computationally effcient formulations for the hub interdiction and
hub protection problems, which are bi-level and tri-level mixed integer linear programs, respec-
tively. In the hub interdiction problem, the aim 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 to the hub-and-
spoke network. Reduction of the bi-level interdiction model to single level is straightforward using
Karush-Kuhn-Tucker (KKT) conditions corresponding to the lower level problem; however, this
turns out to be computationally ineffcient in this context. Therefore, we exploit the structure of
the problem using various closest assignment constraints to reduce the hub interdiction problem
to single level. The modifications lead to computational savings of almost an order of magnitude
when compared against the only model existing in the literature. Further, our proposed modifi-
cations offer structural advantages for Benders decomposition, which lead to substantial savings,
particularly for large problems. Finally, we study and solve the hub protection problem exactly by
utilizing the ideas developed for the hub interdiction problem. The tri-level protection problem is
otherwise intractable, and to our best knowledge, has not been solved in the literature. | en_US |
