  


New solution approaches for the maximumreliability stochastic network interdiction problem
Eli Towle (etowlewisc.edu) Abstract: We investigate methods to solve the maximumreliability stochastic network interdiction problem (SNIP). In this problem, a defender interdicts arcs on a directed graph to minimize an attacker's probability of undetected traversal through the network. The attacker's origin and destination are unknown to the defender and assumed to be random. SNIP can be formulated as a stochastic mixedinteger program via a deterministic equivalent formulation (DEF). As the size of this DEF makes it impractical for solving large instances, current approaches to solving SNIP rely on modifications of Benders decomposition. We present two new approaches to solve SNIP. First, we introduce a new DEF that is significantly more compact than the standard DEF. Second, we propose a new pathbased formulation of SNIP. The number of constraints required to define this formulation grows exponentially with the size of the network, but the model can be solved via delayed constraint generation. We present valid inequalities for this path based formulation which are dependent on the structure of the interdicted arc probabilities. We propose a branchandcut (BC) algorithm to solve this new SNIP formulation. Computational results demonstrate that directly solving the more compact SNIP formulation and this BC algorithm both provide an improvement over a stateoftheart implementation of Benders decomposition for this problem. Keywords: Network interdiction, stochastic programming, integer programming Category 1: Stochastic Programming Category 2: Integer Programming ((Mixed) Integer Linear Programming ) Category 3: Applications  OR and Management Sciences (Other ) Citation: Towle, Eli, and James Luedtke. "New solution approaches for the maximumreliability stochastic network interdiction problem." Computational Management Science 15.34 (2018): 455477. Download: [PDF] Entry Submitted: 08/14/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  