Best Response Intersection: An Optimal Algorithm for Interdiction Defense

We define the interdiction defense problem as a game over a set of targets with three stages: a first stage where the defender protects a subset of targets, a second stage where the attacker observes the defense decision and attacks a subset of targets, and a third stage where the defender optimizes a system using only the surviving targets. We present a novel algorithm for optimally solving such problems that uses repeated calls to an attacker’s best response oracle. For cases where the defender can defend at most k targets and the attacker can attack at most z targets, we prove that the algorithm makes at most $\left(\begin{array}{c}k+z\\ k\end{array}\right)$ calls to the oracle. In application to the direct current optimal power flow problem, we present a new mixed integer programming formulation with bounded big-M values to function as a best response oracle. We use this oracle along with the algorithm to solve a defender-attacker-defender version of the optimal power flow problem. On standard test instances, we find solutions with larger values of k and z than shown in previous studies and with runtimes that are an order of magnitude faster than column and constraint generation.

Funding: This work was sponsored in part by the U.S. Department of Energy Office of Electricity’s Advanced Grid Modeling (AGM) program. This work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory [Contract DE-AC52-07NA27344].