Skip to content

Sequential Network Interdiction with Incomplete Information

Dr. Oleg Prokopyev
Associate Professor of ISE
University of Pittsburgh
September 23, 2016    2:20-3:20pm
JDT 410

 

Abstract:
In network interdiction, an interdictor selects a series of
interdiction measures that change the structure of a network with the objective of disrupting or stopping an evader’s movement through the network. This class of network optimization problems is motivated by military and law-enforcement applications and has received considerable attention during the past decades. While most studies assume complete knowledge of the network structure and costs, in many application settings, the interdictor operates (at least initially) with limited information about the conditions on the ground. In this talk, we envision network interdiction as a sequential process, where the interdictor initially has partial knowledge about the structure and costs of the network, and may adapt the interdiction actions as new information is collected from observing the evader’s reaction to previous actions. We focus our attention on a specific setting, where the interdictor blocks at most k arcs from the network observed up to that period, after which the evader travels along a shortest path between two (fixed) nodes in the interdicted network. By observing the evader’s actions, the interdictor learns about the network structure and arc costs, and adjusts its actions so as to maximize the cumulative cost incurred by the evader. A salient feature of our work is that the feedback in each period is deterministic and adversarial. In addition to studying the regret minimization problem, we also discuss time-stability of a policy, which is the number of time periods until the interdictor’s actions match those of an oracle with prior knowledge of the network. We propose a class of simple interdiction policies that have a finite regret and detect when the instantaneous regret reaches zero in real time. More importantly, we establish that this class of policies belongs to the set of efficient policies. This is a joint work with Juan Borrero (University of Pittsburgh) and Denis Saure (Universidad de Chile).

 

 Bio: Dr. Oleg Prokopyev is an Associate Professor in the Department of Industrial Engineering at the University of Pittsburgh. He received MS and PhD degrees in industrial and systems engineering from the University of Florida and BS and MS degrees in applied mathematics and physics from Moscow Institute of Physics and Technology (Moscow, Russia). Dr. Prokopyev’s primary research interests lie in the areas of combinatorial optimization, stochastic programming and applications of Operations Research in health care and network analysis. His research has been supported by the NSF, AFOSR and DTRA, and he is a recipient of the AFOSR Young Investigator Award. Dr. Prokopyev is a Co-Editor-in-Chief of “Optimization Letters” and serves on editorial boards of “IISE Transactions” and “Journal of Global Optimization.”

 

The flagship campus of the University of Tennessee System and partner in the Tennessee Transfer Pathway.