Runtime Analysis of Benders Decomposition and Dual ILP Algorithms as Applied to Common Network Interdiction Problems
Abstract
Attacker-defender models help practitioners understand a networks resistance to attack. An assailant interdicts a network, and the operator responds in such a way as to optimally utilize the degraded network. This thesis analyzes two network interdiction algorithms, Benders decomposition and a dual integer linear program approach, to compare their computational efficiency on the shortest path and maximum flow interdiction problems. We construct networks using two operationally meaningful structures: a grid structure designed to represent an urban transportation network, and a layered network designed to mimic a supply chain. We vary the size of the network and the attacker's budget and we record each algorithms runtime. Our results indicate that Benders decomposition performs best when solving the shortest path interdiction problem on a grid network, the dual integer linear program performs better for the maximum flow problem on both the grid and layered network, and the two approaches perform comparably when solving the shortest path interdiction problem on the layered network.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 2022
- Accession Number
- AD1184633
Entities
People
- Timothy S. Jr Trask
Organizations
- Naval Postgraduate School