A distributed framework for the minimum cost problem based on graph decomposition☆

Abstract

Controlling a system is a fundamental challenge in real-world applications. Efficient control requires determining the optimal placement of inputs to ensure effective system performance. The Minimum Cost Problem (MCP) aims to minimize control costs by selecting the most effective input locations. However, existing centralized optimization methods for solving the MCP, which rely on global information, face significant challenges, including high computational complexity in large-scale networks and non-convex cost functions that often lead to undesirable local minima. This paper introduces distributed frameworks based on graph decomposition, enabling the application of existing optimization methods in a distributed manner. These frameworks significantly reduce computational complexity and improve scalability. Simulation results on real-world networks demonstrate that the proposed framework significantly outperforms centralized methods in terms of both computational efficiency and energy minimization.