Solution algorithms for shortest path network interdiction with symmetric and asymmetric information

Abstract

We study symmetric and asymmetric models of shortest path network interdiction and propose an algorithm to solve the problem in each case. We consider the situation where the arcs in a network may be interdicted with different levels of intensity, proportional to the budget spent on interdiction. It is assumed in the asymmetric model that the evader’s perception of the interdiction impact is different from that of the interdictor and thus, each player assumes a different objective function. The first algorithm enhances the efficiency of the decomposition based method for the symmetric case by exploiting the problem structure. The second algorithm is devised for solving the asymmetric model and equipped with a customised supplementary procedure to overcome the issue of trapping in a near-optimal solution. Both symmetric and asymmetric models have been solved to optimality using the proposed algorithms. Furthermore, a duality based approach is employed to reformulate both models and solve the resulting problems using a commercial solver. The proposed algorithms significantly outperform the duality based approach for solving large instances and instances with large interdiction budgets.

KEYWORDS:

• Shortest path
• network interdiction
• partial interdiction
• interdiction intensity
• information asymmetry

Data availability statement

The data that support the findings of this study are available from the corresponding author, upon reasonable request.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Notes on contributors

Elnaz Azizi

Elnaz Azizi is a Ph.D. Candidate in the Department of Industrial Engineering and Management Systems at Amirkabir University of Technology in Tehran, Iran. She received her B.Sc. in Applied Mathematics from Kharazmi University in Tehran, Iran and M.Sc. in Industrial Engineering from Amirkabir University of Technology. Her research journey focuses on the intricate areas of bilevel programming, network interdiction, game theory, robust optimization, and data analytics. Through her academic pursuits, Elnaz seeks to unravel the complexities of these fields, contributing valuable insights and bridging the gap between theoretical concepts and practical applications.

Abbas Seifi

Dr Abbas Seifi is a professor of Industrial Engineering and Management Systems at Amirkabir University of Technology in Iran. He did his BASc and MASc in Industrial Engineering at Sharif University of Technology. He received his PhD in Systems Design Engineering from the University of Waterloo in Canada and worked there as a postdoctoral research associate for over 2 years. His teaching and research interests include applied operational research, system dynamics modeling, interior-point method, semidefinite programming, stochastic and robust optimization, reliability-based design and manufacturing yield. He has also experienced various industrial settings and worked as a consultant for many years.