Robust location of hidden interdictions on a shortest path network

Abstract

We study a version of the shortest path network interdiction problem in which the follower seeks a path of minimum length on a network and the leader seeks to maximize the follower’s path length by interdicting arcs. We consider placement of interdictions that are not visible to the follower; however, we seek to locate interdictions in a manner that is robust against the possibility that some information about the interdictions becomes known to the follower. We formulate the problem as a bilevel program and derive some properties of the inner problem, which enables solving the problem optimally via a Benders decomposition approach. We derive supervalid inequalities to improve the performance of the algorithm and test the performance of the algorithm on randomly generated, varying-sized grid networks and acyclic networks. We apply our approach to investigate the tradeoffs between conservative (i.e., the follower discovers all interdiction locations) and risky (i.e., the follower discovers no interdiction locations) assumptions regarding the leader’s information advantage.

Keywords:

• Asymmetric information
• Benders decomposition; Network interdiction
• Shortest path

Acknowledgments

This research is supported by the Arkansas High Performance Computing Center which is funded through multiple National Science Foundation grants and the Arkansas Economic Development Commission. The authors are grateful for the detailed reviews and constructive comments provided by two anonymous referees.

Additional information

Notes on contributors

N. Orkun Baycik

Dr. N. Orkun Baycik is an assistant professor in the Harry F. Byrd, Jr. School of Business at Shenandoah University, Winchester, VA. Dr. Baycik holds a Ph.D. in industrial and systems engineering from Rensselaer Polytechnic Institute and a M.S. in industrial engineering from the University of Arkansas. His research focuses on problems in network optimization and interdiction that have applications in homeland security and supply chain analyses. He is a member of the Institute for Operations Research and the Management Sciences and the Institute of Industrial and Systems Engineers.

Kelly M. Sullivan

Dr. Kelly M. Sullivan is an assistant professor of industrial engineering at the University of Arkansas, Fayetteville, AR. His research focuses on advancing computational methodology for designing, maintaining, and securing complex systems. He holds a Ph.D. in industrial and systems engineering from the University of Florida and a M.S. in industrial engineering from the University of Arkansas. Dr. Sullivan received a National Science Foundation CAREER Award in 2018 and was awarded the 2014 Glover–Klingman Prize for the best paper published in Networks. He is currently a member of IISE and INFORMS and serves as an associate editor for Operations Research Letters and INFORMS Journal on Computing.