  We investigate methods to solve the maximum-reliability 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
mixed-integer 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
path-based 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 branch-and-cut
(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 state-of-the-art implementation of
Benders decomposition for this problem.
