Shortest Path Network Interdiction Model wioth Uncertainty - Bilateral Robust Optimization Approach

Xu Yuanjun

Abstract

Network-based systems participate in various societal and economic areas as fundamental infrastructure frameworks. These interconnected systems span crucial sectors like electrical grids, water supply networks, transportation systems, and telecommunication platforms, enabling coordination and efficient resource management across different industries and communities.

Network interdiction problem refers to the study conducted based on the network being interdicted, attacked, or disrupted. Two agents, one side named interdictor (or attacker) and the other named evader (or defender), are involved in the network interdiction problem, a zero-sum game on a directed network. For the evader, the goal is to reach the sink node from the start node by traversing arcs between nodes. The evaders must pay the corresponding cost associated with each arc they take and minimize their total expenditure, which is their objective function through optimization. For the interdictor, the goal is to maximize the evader's total cost by interdicting certain arcs within a specified budget, which causes the evader’s traversing cost to increase and thus expects to maximize the evader’s expenditure. The origins of the network interdiction problem can be traced back to the military and cybersecurity domains, focusing on how to selectively interrupt or disrupt targets in a network to maximize the impact on an adversary's resources or capabilities. This problem model first appeared in the mid-twentieth century, and was developed and laid a foundation by Fulkerson and Harding with a maximum flow problem (1977). It has evolved into various applications, including optimization of transportation networks, protection of communication networks, and supply chain security.

Contemporary studies have introduced more complex scenarios. These emerging models discuss interdiction problems involving uncertain information, stochastic elements, dynamic interactions between players, simultaneous play, and asymmetric information. These advancements reflect the growing applicability of network interdiction in diverse fields. Robust optimization is one popular variation derived from the classic network interdiction problem.

In robust optimization, the decision maker makes strategies under an uncertain environment. The uncertainty can contribute to the objective function value changes or result in a different feasible region. The optimal solution and corresponding objective function value provide a theoretical worst performance under all possible worst conditions. Specifically, when the optimization is conducted under the interdictor’s view to maximize total cost, with uncertain perception on certain parameters, the robust model gives a solution that provides a lower bound when applied. Any parameters that occur only if they fall in the uncertainty set utilized in the robust optimization model are not able to contribute to a lower objective value than the provided one.

The model in this paper extended the existing model to enable uncertainty information to exist in both the evader side and interdictor side, and verified the validity of the solution.