Convex hull representation of the deterministic bipartite network interdiction problem (Q2248756)

The authors consider an asymmetric bipartite stochastic network interdiction problem. Here, the follower seeks a maximum reliability path (crossing a border) from an unknown origin to an unknown destination through a transportation network. The leader places a limited number of sensors on border crossing arcs in order to minimize the follower's probability of traversing the network successfully. The uncertainty in origin and destination is modelled by optimizing against a number of followers. The authors present a formulation for the one opponent model and through developing several classes of facet defining inequalities, provide a convex hull representation of the associated polyhedron. They also show how to derive a representation of \(\mathrm{conv}(P)\) through the special structures reformulation-linearization technique. Finally, they discuss extensions of their results for the multiple opponent problem and present some computational results.