Groupe d’études et de recherche en analyse des décisions

A Fast Heuristic for Optimal Transmission Switching

David Fuller University of Waterloo, Canada

Recently, Hedman, Fisher, O'Neill, Oren, et al. have defined a mixed integer linear program (MILP) for the short-term, least cost generation of electricity to meet demand on a transmission network, while allowing for the reconfiguration of the network by switching some transmission lines out of service (corresponding to binary variables with value zero). At first sight, it seems counter-intuitive that "reducing capacity" of the transmission network (by removing lines from service) could help to reduce costs, but in fact, this can lead to significant cost reductions, compared to leaving all lines in service. There are several obstacles to the implementation of the idea of Hedman et al., one of which is the topic of the presentation: the MILP of Hedman et al. takes far too long to solve (e.g., the better part of a day) to be of practical use for decisions that must be made within a few minutes.

The presentation will derive the MILP, and review the testing done by Hedman et al. A heuristic defined by Hedman et al. will be defined, involving the solution of a sequence of MILPs, each one of which removes the one line which reduces generation cost the most. Then a new heuristic will be presented, based on solving a sequence of linear programs (i.e., no binary variables), with one more line taken out of service at each step in the sequence, based on information extracted from the dual variables of the last LP solved. Some computational tests of the two heuristics (MILP and LP based) will be presented.

The MILP and LP based methods depend on a linear approximation of the exact representation of power flow on a transmission network. One of the inaccuracies in the linear approximation is that resistance losses on lines are supposedly zero. A more accurate model represents nonzero resistance loss on a line as proportional to the square of power flow on the line. Applied to the line switching problem, the resulting model is a mixed integer nonlinear program, which is likely to be even more difficult to solve than the less accurate MILP. The last part of the presentation will examine the extension of the "sequence of LPs" heuristic to a sequence of nonlinear programs.