A Backward Sampling Framework for Interdiction Problems with Fortification

Leonardo Lozano () and J. Cole Smith ()
Additional contact information
Leonardo Lozano: Department of Industrial Engineering, Clemson University, Clemson, South Carolina 29634
J. Cole Smith: Department of Industrial Engineering, Clemson University, Clemson, South Carolina 29634

INFORMS Journal on Computing, 2017, vol. 29, issue 1, 123-139

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.

Keywords: polynomial discrete program; mixed-integer linear program; linearization equation; branch and bound (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2016.0721 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:29:y:2017:i:1:p:123-139

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().