A graph-based iterative strategy for solving the all-line transmission switching problem

Abstract The transmission switching problem aims to determine the optimal network topology that minimizes the operating costs of a power system. This problem is typically formulated as a mixed-integer optimization model, which involves big-M constants that lead to weak relaxations and significant computational challenges, particularly when all lines are switchable. In this paper, we propose a twofold approach: first, using graph theory to derive tighter big-M values by solving a relaxed longest path problem; second, introducing an iterative algorithm that incorporates a heuristic version of the switching problem to efficiently generate low-cost feasible solutions, thereby accelerating the search for optimal solutions in the integer optimization solver. Numerical results on the 118-bus network across 100 demand scenarios demonstrate that the proposed methodology reduces the number of unsolved instances within 1 h by 57% and decreases the average computational time by 44% compared to conventional approaches in the literature.