Multiple allocation hub interdiction and protection problems: model formulations and solution approaches

Abstract

In this paper, we present computationally efficient formulations for the multiple allocation hub interdiction and hub protection problems, which are bilevel and trilevel mixed integer linear programs, respectively. In the hub interdiction problem, the aim is to identify a subset of r critical hubs from an existing set of p hubs that when interdicted results in the maximum post-interdiction cost of routing flows. We present two alternate ways of reducing the bilevel hub interdiction model to a single level optimization problem. The first approach uses the dual formulation of the lower level problem. The second approach exploits the structure of the lower level problem to replace it by a set of closest assignment constraints (CACs). We present alternate sets of CACs, study their dominance relationships, and report their computational performances. Further, we propose refinements to CACs that offer computational advantages of an order-of-magnitude compared to the one existing in the literature. Further, our proposed modifications offer structural advantages for Benders decomposition, which lead to substantial computational savings, particularly for large problem instances. Finally, we study and solve large scale instances of the trilevel hub protection problem exactly by utilizing the ideas developed for the hub interdiction problem.