In this paper, we study a network interdiction problem on a multiple allocation, uncapacitated hub network. The problem is formulated as a bilevel Stackelberg game between an attacker and a defender, where the attacker identifies r out of p hubs to interdict so as to maximize the worst-case post-interdiction performance of the system with the surviving hubs. We study three variants of the problem, namely, the r-hub median interdiction problem, the r-hub cen- ter interdiction problem, and the r-hub maximal covering interdiction problem. The bilevel problems are reduced to single-level mixed integer programs (MIP) using dual and penalty- based formulations. We exploit the properties of the models to present tighter single-level MIP formulations. We compare the linear programming relaxations of dual and penalty-based for- mulations to establish the dominance relations between them. Our theoretical analysis shows that the single-level dual formulations of all the three problems are stronger than their cor- responding penalty-based formulations. We validate these theoretical results using extensive computational experiments on moderate to large-scale instances. Our computational results on networks with up to 200 nodes and 15 hubs confirm the strength of the proposed formulations.
Article
View Efficient Formulations for Multiple Allocation Hub Network Interdiction Problems