Exact algorithms and bounds for the dynamic assignment interdiction problem

Jorge A. Sefair, J. Cole Smith

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

We study a multi-stage dynamic assignment interdiction (DAI) game in which two agents, a user and an attacker, compete in the underlying bipartite assignment graph. The user wishes to assign a set of tasks at the minimum cost, and the attacker seeks to interdict a subset of arcs to maximize the user's objective. The user assigns exactly one task per stage, and the assignment costs and interdiction impacts vary across stages. Before any stage commences in the game, the attacker can interdict arcs subject to a cardinality constraint. An interdicted arc can still be used by the user, but at an increased assignment cost. The goal is to find an optimal sequence of assignments, coupled with the attacker's optimal interdiction strategy. We prove that this problem is strongly NP-hard, even when the attacker can interdict only one arc. We propose an exact exponential-state dynamic-programming algorithm for this problem as well as lower and upper bounds on the optimal objective function value. Our bounds are based on classical interdiction and robust optimization models, and on variations of the DAI game. We examine the efficiency of our algorithms and the quality of our bounds on a set of randomly generated instances.

Original languageEnglish (US)
Pages (from-to)373-387
Number of pages15
JournalNaval Research Logistics
Volume64
Issue number5
DOIs
StatePublished - Aug 2017
Externally publishedYes

Keywords

  • assignment problem
  • dynamic programming
  • network interdiction
  • robust optimization

ASJC Scopus subject areas

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Exact algorithms and bounds for the dynamic assignment interdiction problem'. Together they form a unique fingerprint.

  • Cite this