期刊
INFORMS JOURNAL ON COMPUTING
卷 29, 期 1, 页码 123-139出版社
INFORMS
DOI: 10.1287/ijoc.2016.0721
关键词
interdiction; fortification; shortest path problem; capacitated lot sizing problem
资金
- Defense Threat Reduction Agency [HDTRA-10-01-0050]
- Air Force Office of Scientific Research [FA9550-12-1-0353]
- Office of Naval Research [N000141310036]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据