Optimal Decomposition of Large-Scale Networks

Abstract

The underlying concept of decomposition here is that a large complex system representing many interacting elements is broken into subsystems of lower dimensionality. These subsystems are then treated independently for whatever the purpose-optimization, control, design, etc.-in consideration of interconnections between subsystems. The collection of solutions is the solution of the large original problem. In the optimal network decomposition, an attempt is made to minimize the number of interacting elements between subnetworks subject to a size limit on each subnetwork. The problem is formulated in terms of graph theory and dynamic programming. A theorem to solve the problem is developed. Implementation of the theorem in Fortran to apply to the power flow problem of electric power systems and the shortest path problem of street networks is discussed along with the results.