Graph-theoretic optimization models for connectivity enhancement in interconnected engineering networks

Abstract

Networks of engineering systems become increasingly subject to failures of their components, uncertain operating environments, degradation of capacity, and scarcity of resources for their reinforcement. Thus, connectivity becomes an important issue in engineering systems design. This study introduces a minimax graph-theoretic optimization approach for designing interconnected engineering networks in the presence of adverse conditions. An engineering system is modeled by a weighted graph where nodes correspond to the engineering objects while edges describe connections between them. Several metrics of connectivity, such as algebraic connectivity, edge connectivity, node connectivity, network reliability, and average path length, are used for the purpose of assessing the performance and operation of the engineering network. The uncertain set is introduced to account for uncertainties in component availabilities, link failures, and capacity. The minimax problem finds enhancement actions to minimize the worst-case deterioration of connectivity subject to budget, capacity, redundancy, and engineering constraints. The solution method uses alternating iterations of finding the worst-case and optimizing the network for connectivity.  Results have shown that reinforcement through strategic targeting can significantly increase structural robustness in connectivity and help to sustain stable performance in adverse situations. Through sensitivity and comparative analysis, the effect of uncertainty size, failure size, network density, connectivity, and budget for reinforcement has been shown. The proposed framework offers a mathematical method for robust network improvement using cost-effective means and can be used for reinforcing infrastructures and networks, communication robustness, interconnecting power grids, and transportation systems.