A K-Nearest Neighbor Heuristic for Real-Time DC Optimal Transmission Switching

While transmission switching is known to reduce generation costs, the difficulty of solving even dc optimal transmission switching (DCOTS) has prevented optimal transmission switching from becoming commonplace in real-time power systems operation. In this paper, we present a k-nearest neighbors (KNN) heuristic for DCOTS which relies on the insight that, for routine operations on a fixed network, the DCOTS solutions for similar load profiles and generation cost profiles will likely open similar sets of lines. Our heuristic assumes that we have DCOTS solutions for many historical instances. Given a new instance, we find a set of "close" instances from the past and return the best of their solutions for the new instance. We present a case study on the IEEE 118 bus system, the 1354 bus PEGASE system, and the 2869 bus PEGASE system. We compare the proposed heuristic to DCOTS heuristics from the literature, to Gurobi's heuristics, and to the result from a simple greedy local search algorithm. In most cases, we find better quality solutions in less computational time. In addition, the computational time is within the limits imposed by real-time operations, even on larger networks.