Journal
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
Volume 57, Issue 1, Pages 71-104Publisher
SPRINGER
DOI: 10.1007/s10589-013-9589-9
Keywords
Integer programming; Cutting planes; Network optimization; Interdiction; Fortification
Funding
- National Science Foundation [CMMI-1100765, CAREER 0953284]
- Defense Threat Reduction Agency [HDTRA-10-01-0050]
- Air Force Office of Scientific Research [FA9550-12-1-0353]
- Office of Naval Research [N000141310036]
Ask authors/readers for more resources
We consider a two-stage defender-attacker game that takes place on a network, in which the attacker seeks to take control over (or influence) as many nodes as possible. The defender acts first in this game by protecting a subset of nodes that cannot be influenced by the attacker. With full knowledge of the defender's action, the attacker can then influence an initial subset of unprotected nodes. The influence then spreads over a finite number of time stages, where an uninfluenced node becomes influenced at time t if a threshold number of its neighbors are influenced at time t-1. The attacker's objective is to maximize the weighted number of nodes that are influenced over the time horizon, where the weights depend both on the node and on the time at which that is influenced. This defender-attacker game is especially difficult to optimize, because the attacker's problem itself is NP-hard, which precludes a standard inner-dualization approach that is common in many interdiction studies. We provide three models for solving the attacker's problem, and develop a tailored cutting-plane algorithm for solving the defender's problem. We then demonstrate the computational efficacy of our proposed algorithms on a set of randomly generated instances.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available