A backward sampling framework for interdiction problems with fortification

Leonardo Lozano, J. Cole Smith

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

This paper examines a class of three-stage sequential defender-attacker-defender problems. In these problems the defender first selects a subset of assets to protect, the attacker next damages a subset of unprotected assets in the "interdiction" stage, after which the defender optimizes a "recourse" problem over the surviving assets. These problems are notoriously difficult to optimize, and almost always require the recourse problem to be a convex optimization problem. Our contribution is a new approach to solving defender-attacker-defender problems. We require all variables in the first two stages to be binary-valued, but allow the recourse problem to take any form. The proposed framework focuses on solving the interdiction problem by restricting the defender to select a recourse decision from a sample of feasible vectors. The algorithm then iteratively refines the sample to force finite convergence to an optimal solution. We demonstrate that our algorithm not only solves interdiction problems involving NP-hard recourse problems within reasonable computational limits, but it also solves shortest path fortification and interdiction problems more efficiently than state-of-the-art algorithms tailored for that problem, finding optimal solutions to real-road networks having up to 300, 000 nodes and over 1, 000, 000 arcs.

Original languageEnglish (US)
Pages (from-to)123-139
Number of pages17
JournalINFORMS Journal on Computing
Volume29
Issue number1
DOIs
StatePublished - Dec 1 2017
Externally publishedYes

Keywords

  • Capacitated lot sizing problem
  • Fortification
  • Interdiction
  • Shortest path problem

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'A backward sampling framework for interdiction problems with fortification'. Together they form a unique fingerprint.

  • Cite this