A defender-attacker model and algorithm for maximizing weighted expected hitting time with application to conservation planning

ABSTRACT

This article studies an interdiction problem in which two agents with opposed interests, a defender and an attacker, interact in a system governed by an absorbing discrete-time Markov chain. The defender protects a subset of transient states, whereas the attacker targets a subset of the unprotected states. By changing some of the transition probabilities related to the attacked states, the attacker seeks to minimize the Weighted Expected Hitting Time (WEHT). The defender seeks to maximize the attacker’s minimum possible objective, mitigating the worst-case WEHT. Many applications can be represented by this problem; this article focuses on conservation planning. We present a defender–attacker model and algorithm for maximizing the minimum WEHT. As WEHT is not generally a convex function of the attacker’s decisions, we examine large-scale integer programming formulations and first-order approximation methods for its solution. We also develop an algorithm for solving the defender’s problem via mixed-integer programming methods augmented by supervalid inequalities. The efficacy of the proposed solution methods is then evaluated using data from a conservation case study, along with an array of randomly generated instances.

KEYWORDS:

• Network interdiction
• Markov chains
• expected hitting time
• time to absorption
• conservation planning

Acknowledgments

The authors are grateful for the detailed comments of an Associate Editor and two reviewers, whose remarks helped to improve the article’s exposition.

Additional information

Funding

Dr. Smith was supported by the Defense Threat Reduction Agency under grant HDTRA-10-01-0050, the Air Force Office of Scientific Research under grant FA9550-12-1-0353, and the Office of Naval Research under grant N000141310036.

Notes on contributors

Jorge A. Sefair

Jorge A. Sefair is an Assistant Professor in the School of Computing, Informatics, and Decision Systems Engineering at Arizona State University. He received his Ph.D. in industrial and systems engineering from the University of Florida in 2015. His research interests include network optimization, multistage optimization, and integer programming. In particular, he is motivated by applications of operations research in environmental planning, public policy, and urban planning. His research has been interdisciplinary, having published academic works with colleagues from a variety of fields, including civil engineering, public health, ecology, biology, and economics. In 2015, Sefair was awarded the University of Florida Department of Industrial and Systems Engineering graduate student research award and was a runner-up in the INFORMS Computing Society student paper award.

J. Cole Smith

J. Cole Smith is Professor and Chair of the Industrial Engineering Department at Clemson University. His research has been supported by the NSF, DARPA, AFOSR, DTRA, and the ONR, and he has spent one summer as a Distinguished Visiting Professor in the National Security Agency’s summer program in operations research technology. His research regards mathematical optimization models and algorithms, especially those arising in combinatorial optimization. His awards include the Young Investigator Award from the ONR, the Hamid K. Elden Outstanding Young Industrial Engineer in Education Award, the Operations Research Division Teaching Award, the 2014 GloverKlingman prize for best paper in Networks, and the Best Paper Award from IIE Transactions in 2007.

Miguel A. Acevedo

Miguel A. Acevedo is an Assistant Professor of quantitative ecology in the Department of Biology at the University of Puerto Rico in Río Piedras. He received his Ph.D. in interdisciplinary ecology from the School of Natural Resources and Environment at the University of Florida. He follows an interdisciplinary approach to ecology where he combines mathematical modeling with field data to study the interaction between spatial heterogeneity and ecological processes. He is particularly interested in studying metapopulation dynamics, landscape connectivity, the evolution of life-history traits, and host–parasite interactions.

Robert J. Fletcher

Robert J. Fletcher, Jr. is an Associate Professor in the Department of Wildlife Ecology and Conservation at the University of Florida. He received his Ph.D. in ecology with a minor in statistics from Iowa State University in 2003. His research interests include landscape ecology, conservation biology, and quantitative modeling.