Polynomial-time identification of robust network flows under uncertain arc failures

We propose Linear Programming (LP)-based solution methods for network flow problems subject to multiple uncertain arc failures, which allow finding robust optimal solutions in polynomial time under certain conditions. We justify this fact by proving that for the considered class of problems under uncertainty with linear loss functions, the number of entities in the corresponding LP formulations is polynomial with respect to the number of arcs in the network. The proposed formulation is efficient for sparse networks, as well as for time-critical networked systems, where quick and robust decisions play a crucial role.