Back to search

University of Central Florida

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

Abstract

dc:description.abstract

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.

Degree

thesis:*
Grantor dc:publisher
University of Central Florida

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chen, Cheng-Lung
Contributors dc:contributor
  • Boginski, Vladimir

Subjects

dc:subject × 3

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
CFE0008958; DP0026291

Chain of custody

source
Harvested from
Central Florida
Base URL
stars.library.ucf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Chen, Cheng-Lung. Mixed-integer Programming Methods for Modeling and Optimization of Cascading Processes in Complex Networked Systems. University of Central Florida, https://stars.library.ucf.edu/etd2020/987