The capacitated r-hub interdiction problem with congestion: Models and solution approaches

Abstract

We study the r-hub interdiction problem under the case of possible congestion. Hub interdiction problems are modeled as attacker-defender problems to identify a set of r critical hubs from a set of p hubs, which when attacked, causes maximum damage to network restoration activities of the defender. In this work we consider that in addition to the routing cost, the defender also aims to minimize the congestion cost. Incorporating the congestion cost in the problem introduces non-linearity in the objective function of the interdiction problem, which makes the problem challenging to solve. To address this, we propose two alternate exact solution approaches. The first approach is an inner-approximation-based approach (IBA), which overestimates the convex non-linear objective function and provides an upper bound. A lower bound is obtained from solving the lower-level problem exactly corresponding to the upper bound solution. The upper bound is tightened using improved approximation with new points generated in successive iterations. In the second approach (referred to as SBA), the problem is reformulated as a second-order conic program, which can be solved using an off-the-shelf solver. From our computational experiments on benchmark datasets (CAB and AP), we demonstrate the efficacy of both the proposed methods. However, IBA consistently outperforms SBA by a significant margin.