A cutting-plane algorithm for solving a weighted influence interdiction problem

Mehdi Hemmati, J. Cole Smith, My T. Thai

Research output: Contribution to journalArticle

8 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)71-104
Number of pages34
JournalComputational Optimization and Applications
Volume57
Issue number1
DOIs
StatePublished - Jan 1 2014
Externally publishedYes

Keywords

  • Cutting planes
  • Fortification
  • Integer programming
  • Interdiction
  • Network optimization

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A cutting-plane algorithm for solving a weighted influence interdiction problem'. Together they form a unique fingerprint.

  • Cite this