RUNTIME ANALYSIS OF BENDERS DECOMPOSITION AND DUAL ILP ALGORITHMS AS APPLIED TO COMMON NETWORK INTERDICTION PROBLEMS

Thumbnail Image
Files
22Jun_Trask_Timothy.pdf (8.93 MB)
Authors
Trask, Timothy S., Jr.
Subjects
network interdiction
Benders decomposition
integer linear program
ILP
dual ILP
integer linear program
runtime
Advisors
Craparo, Emily M.
Date of Issue
2022-06
Date
Publisher
Monterey, CA; Naval Postgraduate School
Language
Abstract
Attacker-defender models help practitioners understand a network’s 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 algorithm’s 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.
Type
Thesis
Description
Reissued 20 Nov 2023 to update verbiage on page 18.
URI
https://hdl.handle.net/10945/70770
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
Approved for public release. Distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Collections
Theses
Load more