Faster Solutions to the Interdiction Defense Problem using Suboptimal Solutions

The interdiction defense (ID) problem solves a defender-attacker-defender model where the defender and attacker share the same set of components to harden and target. We build upon the best response intersection (BRI) algorithm by developing the BRI with suboptimal solutions (BRI-SS) algorithm to solve the ID problem. The BRI-SS algorithm utilizes off-the-shelf optimization solvers that may return suboptimal solutions at no additional computation cost. We derive novel cuts from suboptimal solutions, generally reducing the number of iterations required for the algorithm to converge while maintaining optimality guarantees. We also present a heuristic that utilizes all obtained suboptimal solutions to select the next defense to evaluate at each iteration of the algorithm. We perform computational experiments applied to power grid interdiction on standard test cases. Our results demonstrate that the BRI-SS algorithm consistently outperforms the BRI algorithm across all test cases.

Article

Download

View PDF