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


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.

IISE Transactions
Click the Cite button above to import publication metadata into your reference management software.
Miguel Acevedo
Miguel Acevedo
Assistant Professor of Quantitative Wildlife Population Ecology

My research interests include global change, lizard malaria, and quantitative applications for conservation planning.