Interdicting layered physical and information flow networks

ABSTRACT

This article focuses on the problem of interdicting layered networks that involve a physical flow network and an information flow network. There exist dependencies between these networks since components of the physical flow network are only operational should their counterparts in the information flow network receive enough demand. This leads to a network interdiction problem over these layered networks. The objective of the defender is to send the maximum amount of flow through its physical flow network. The objective of the attacker is to interdict components within the layered networks to minimize this maximum flow. For the case where the information supply arcs are uncapacitated, we apply a novel multi-step, dual-based reformulation technique. We apply this reformulation technique to two applications in order to provide policy-driven analysis: law enforcement efforts against illegal drug trafficking networks and cyber vulnerability analysis of infrastructure and supply chain networks. The computational results prove that our reformulation technique outperforms the traditional duality-based reformulation technique by orders of magnitude. This allows us to analyze instances of realistic size.

KEYWORDS:

• Network interdiction
• interdependent layered networks
• illegal drug supply chains
• cyber vulnerability analysis

Acknowledgements

The authors thank the reviewers and editors for their remarks that led to a clearer presentation of the results and justification of the uncapacitated information flow network.

Additional information

Funding

This research was partially supported by the U.S. National Science Foundation under grant number CMMI-1266084.

Notes on contributors

Nail Orkun Baycik

Nail Orkun Baycik earned an M.Sc. degree in Industrial Engineering from the University of Arkansas in 2014. He is currently a Ph.D. student in the Department of Industrial and Systems Engineering at Rensselaer Polytechnic Institute. His research focuses on problems in network optimization and interdiction that have applications in homeland security and supply chain analyses. Orkun is a member of the Institute for Operations Research and the Management Sciences (INFORMS) and the Institute of Industrial and Systems Engineers (IISE).

Thomas C. Sharkey

Thomas C. Sharkey is an Associate Professor in the Department of Industrial and Systems Engineering at Rensselaer Polytechnic Institute. His research interests are in creating operations research models and algorithms for applications in public policy and homeland security. His research has been funded through multiple NSF awards, including a CAREER award, and through the Department of Homeland Security.

Chase E. Rainwater

Chase E. Rainwater is an Associate Professor in the Department of Industrial Engineering at the University of Arkansas. Chase received his Ph.D. in Industrial and Systems Engineering from the University of Florida. His primary research is in large-scale optimization, security, and supply chain logistics.