Integer programming methods for solving binary interdiction games

This paper studies a general class of interdiction problems in which the solution space of both the leader and follower are characterized by two discrete sets denoted the leader's strategy set and the follower's structure set. In this setting, the interaction between any strategy-structure pair is assumed to be binary, in the sense that the strategy selected by the leader either interacts or not with the follower's choice of structure and, if it does, then the structure becomes unavailable for the follower. There are many interdiction games defined by this setup, including problems where the leader wishes to attack some type of network structures, such as shortest paths, minimum spanning trees, and minimum dominating sets, among others. We study a general set-covering type of formulation that can be used for solving this class of problems and analyze several properties of the convex hull of its solutions. We develop a wide class of valid inequalities that generalizes and extends several others that have appeared in the literature in recent years. We provide conditions for them to be facet-defining and conclude with a general discussion about their separation. Several examples of problems in the context of network interdiction are presented to help with the exposition.