Art Original
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 (k+zk)
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.
Barcode | Tipe Koleksi | Nomor Panggil | Lokasi | Status | |
---|---|---|---|---|---|
art146272 | null | Artikel | Gdg9-Lt3 | Tersedia namun tidak untuk dipinjamkan - No Loan |
Tidak tersedia versi lain