Mixed-integer Programming Methods for Modeling and Optimization of Cascading Processes in Complex Networked Systems

Dynamics and growth of many natural and man-made systems can be represented by large-scale complex networks. Entity interactions and community interconnections within complex networks increase the level of difficulty for the investigation on structural network properties such as robustness, vulnerability and resilience. In this dissertation, we develop methodologies based on mixed-integer programming techniques to solve challenging optimization problems that model cascading processes in complex networked systems. In particular, we seek to provide decision making recommendations for problems related to different types of cascading processes in networks commonly considered in a variety of applications: interdependent infrastructure networks and social networks. In the first part, we propose a novel optimization model to enhance the resilience against cascading failure by mitigation and restoration in interdependent networks. We derive a polynomial class of valid inequalities from the cascading constraints and reformulate the substructure that describes capacity restriction to guarantee integral solutions. The computational experiments illustrate that our strengthened formulation outperforms the default setting of a commercial solver on all tested instances. Next, we study the least cost influence maximization problem that arises in social network analytics. We investigate the polyhedral properties of a substructure that is a relaxation of the mixed 0-1 knapsack polyhedron. We give three exponential class of facet-defining inequalities from this substructure and an exact polynomial time separation algorithm for the inequalities. In addition, we propose another new class of strong valid inequalities that dominates the cycle elimination constraints. Through the computational experiments, we demonstrate that a delayed cut generation algorithm that exploits these inequalities is very effective to solve the problem under different settings of network size, density and connectivity