Title: A cycle-based formulation and valid inequalities for DC power transmission problems with switching
Speaker: Prof. Jeff Linderoth
Affiliation: Departments of Industrial and Systems Engineering and Computer Sciences (by courtesy) – University of Wisconsin-Madison
Location: LT 145 Huxley Building
Time: 3:00pm
Abstract. It is well-known that optimizing network topology by switching on and off transmission lines improves the efficiency of power delivery in electrical networks. Many authors have studied the problem of determining an optimal set of transmission lines to switch off to minimize the cost of meeting a given power demand under the direct current (DC) model of power flow. This problem is known in the literature as the Direct-Current Optimal Transmission Switching Problem (DC-OTS). Most research on DC-OTS has focused on heuristic algorithms for generating quality solutions or on the application of DC-OTS to crucial operational and strategic problems. The mathematical theory of the DC-OTS problem is less well-developed. In this work, we formally establish that DC-OTS is NP-Hard, even if the power network is a series-parallel graph with at most one load/demand pair. Inspired by Kirchoff’s Voltage Law, we give a cycle-based formulation for DC-OTS, and we use the new formulation to build a cycle-induced relaxation. We characterize the convex hull of the cycle-induced relaxation, and the characterization provides strong valid inequalities that can be used in a cutting-plane approach to solve the DC-OTS. We give details of a practical implementation, and we show promising computational results on standard benchmark instances.
Co-authors:
This is joint work with: Burak Kocuk, Santanu Dey, Andy Sun (Georgia Tech), Hyemin Jeon, and Jim Luedtke (Wisconsin)
About the speaker. Jeff Linderoth is a Professor in the departments of Industrial and Systems Engineering and Computer Sciences (by courtesy) at the University of Wisconsin-Madison, joining both departments in 2007. Dr. Linderoth received his Ph.D. degree from the Georgia Institute of Technology in 1998. He was awarded an an Early Career Development Award from the Department of Energy, and he has won the SIAM/Activity Group on Optimization Prize and the INFORMS Computing Society ICS Prize. Dr. Linderoth currently serves on the editorial boards of 4 journals, including Operations Research and Mathematical Programming Computation.