Mechanical and Civil Engineering Seminar

This talk addresses the design of monitoring systems to improve the resilience of large-scale infrastructures against natural events and malicious disruptions. First, we present optimal sensor placement algorithms for location identification of random faults in pipeline networks. The identification problem is shown to be an instance of the set (multi)cover problem, and a greedy heuristic is used to obtain efficient solutions. Second, we address the problem of finding a (randomized) sensing strategy utilizing the minimum number of sensors necessary to ensure a desired detection performance in the presence of a malicious adversary who can target the network at multiple locations.  This problem can be formulated as a mathematical program with constraints involving the Nash equilibria of a network security game, and can be solved using the solutions to two problems: a minimum set cover and a maximum set packing problem.  Finally, we introduce a stochastic probing problem for finding the optimal sequence of locations to inspect for possible failures in the aftermath of a natural event. Our solution captures the key exploration/exploitation trade-off faced by inspection teams in choosing their routes. These results demonstrate the value of utilizing the physical properties of network disruptions in solving the underlying combinatorial optimization problems.