  The recent advancement in real-world critical infrastructure networks has led
to an exponential growth in the use of automated devices which in turn has
created new security challenges. In this paper, we study the robust and
adaptive maximum flow problem in an uncertain environment where the network
parameters (e.g., capacities) are known and deterministic, but the network
structure (e.g., edges) is vulnerable to adversarial attacks or failures. We
propose a robust and sustainable network flow model to effectively and
proactively counter plausible attacking behaviors of an adversary operating
under a budget constraint. Specifically, we introduce a novel scenario
generation approach based on an iterative two-player game between a defender
and an adversary. We assume that the adversary always takes a best myopic
response (out of some feasible attacks) against the current flow scenario
prepared by the defender. On the other hand, we assume that the defender
considers all the attacking behaviors revealed by the adversary in previous
iterations in order to generate a new conservative flow strategy that is robust
(maximin) against all those attacks. This iterative game continues until the
objectives of the adversary and the administrator both converge. We show that
the robust network flow problem to be solved by the defender is NP-hard and
that the complexity of the adversary's decision problem grows exponentially
with the network size and the adversary's budget value. We propose two
principled heuristic approaches for solving the adversary's problem at the
scale of a large urban network. Extensive computational results on multiple
synthetic and real-world data sets demonstrate that the solution provided by
the defender's problem significantly increases the amount of flow pushed
through the network and reduces the expected lost flow over four
state-of-the-art benchmark approaches.
