Modeling and optimization techniques for ensuring resilience in heterogeneous networked systems

This dissertation presents modeling and optimization approaches for addressing some aspects of ensuring resilience of various types of networked systems with respect to potential failures of network components. In the context of the considered problems, resilience of a networked system can be broadly defined as the ability of a system to maintain its functionality after intentional attacks or unintentional (random) failures of system components (i.e., nodes and/or links). Many real-world systems and infrastructures can be modelled as heterogeneous networks, which can be considered either separately, or as parts of larger interdependent networked systems, which may include power, communication, transportation and other types of networks that may mutually interact and affect each other's performance. After a brief introduction to the resilience of heterogeneous networked systems in the first part of this dissertation, the second part studies a transmission expansion planning problem for interdependent electricity and natural gas systems. Electricity generation is one of the largest natural gas consumption. Natural gas is playing an increasingly important role in the global energy market because of its environment friendly properties, especially for electricity generation. We study a stochastic transmission expansion planning model, which considers expansion of electricity generation and transmission, as well as natural gas transmission and LNG terminals location planning. The third part of the dissertation addresses optimization models for network topology design that enable end-to-end dual-path support in a distributed wireless sensor network. We consider the case of a stationary sensor network with isotropic antennas, where the control variable for topology management is the transmission power on network nodes. For optimization modeling, the network metrics of relevance are coverage, robustness and power utilization. The forth part of the dissertation considers a formulation for the fixed charge network flow (FCNF) problem subject to multiple uncertain arc failures, which aims to provide a robust optimal flow assignment in the sense of restricting potential losses using Conditional Value-at-Risk. We show that a heuristic algorithm referred to as Adaptive Dynamic Cost Updating Procedure previously developed for the deterministic FCNF problem can be extended to the considered problem under uncertainty and produce high-quality heuristic solutions for large problem instances. The reported computational experiments demonstrate that the described procedure can successfully tackle both the uncertainty considerations and the large size of the networks. Finally, the fifth part of this dissertation considers a specific aspect of resilience analysis of a system of two interdependent networks in terms of finding critical components, which removal minimizes pairwise connectivity of the remaining networks, as well as identifying an exact minimum-cardinality set of nodes, whose removal completely disconnects both networks. Our results generalize some of the well-known properties of the critical nodes and minimum vertex cover problems. We study two types of interdependencies that are common, for instance, in telecommunication and energy supply contexts.