Zheng, Jiefu2015-04-272015-04-2720132013https://hdl.handle.net/2144/11094Thesis (Ph.D.)--Boston UniversityNetwork interdiction problems consist of games between an attacker and an intelligent network, where the attacker seeks to degrade network operations while the network adapts its operations to counteract the effects of the attacker. This problem has received significant attention in recent years due to its relevance to military problems and network security. When the attacker's actions achieve uncertain effects, the resulting problems become stochastic network interdiction problems. In this thesis, we develop new algorithms for the solutions of different classes of stochastic network interdiction problems. We first focus on static network interdiction games where the attacker attacks the network once, which will change the network with certain probability. Then the network will maximize the flow from a given source to its destination. The attacker is seeking a strategy which minimizes the expected maximum flow after the attack. For this problem, we develop a new solution algorithm, based on parsimonious integration of branch and bound techniques with increasingly accurate lower bounds. Our method obtains solutions significantly faster than previous approaches in the literature. In the second part, we study a multi-stage interdiction problem where the attacker can attack the network multiple times, and observe the outcomes of its past attacks before selecting a current attack. For this dynamic interdiction game, we use a model-predictive approach based on a lower bound approximation. We develop a new set of performance bounds, which are integrated into a modified branch and bound procedure that extends the single stage approach to multiple stages. We show that our new algorithm is faster than other available methods with simulated experiments. In the last part, we study the nested information game between an intelligent network and an attacker, where the attacker has partial information about the network state, which refers to the availability of arcs. The attacker does not know the exact state, but has a probability distribution over the possible network states. The attacker makes several attempts to attack the network and observes the flows on the network. These observations will update the attacker's knowledge of the network and will be used in selecting the next attack actions. The defender can either send flow on that arc if it survived, or refrain from using it in order to deceive the attacker. For these problems, we develop a faster algorithm, which decomposes this game into a sequence of subgames and solves them to get the equilibrium strategy for the original game. Numerical results show that our method can handle large problems which other available methods fail to solve.en-USThesis/Dissertation