A Caltech Library Service

Graphical models for optimal power flow

Dvijotham, Krishnamurthy and Chertkov, Michael and Van Hentenryck, Pascal and Vuffray, Marc and Misra, Sidhant (2017) Graphical models for optimal power flow. Constraints, 22 (1). pp. 24-49. ISSN 1383-7133. doi:10.1007/s10601-016-9253-y.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Optimal power flow (OPF) is the central optimization problem in electric power grids. Although solved routinely in the course of power grid operations, it is known to be strongly NP-hard in general, and weakly NP-hard over tree networks. In this paper, we formulate the optimal power flow problem over tree networks as an inference problem over a tree-structured graphical model where the nodal variables are low-dimensional vectors. We adapt the standard dynamic programming algorithm for inference over a tree-structured graphical model to the OPF problem. Combining this with an interval discretization of the nodal variables, we develop an approximation algorithm for the OPF problem. Further, we use techniques from constraint programming (CP) to perform interval computations and adaptive bound propagation to obtain practically efficient algorithms. Compared to previous algorithms that solve OPF with optimality guarantees using convex relaxations, our approach is able to work for arbitrary tree-structured distribution networks and handle mixed-integer optimization problems. Further, it can be implemented in a distributed message-passing fashion that is scalable and is suitable for “smart grid” applications like control of distributed energy resources. Numerical evaluations on several benchmark networks show that practical OPF problems can be solved effectively using this approach.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper ReadCube access
Dvijotham, Krishnamurthy0000-0002-1328-4677
Misra, Sidhant0000-0003-1738-6635
Additional Information:© 2016 Springer International Publishing Switzerland. Published online: 13 September 2016. This work was supported by Skoltech through collaboration agreement 1075-MRA. The work at LANL was carried out under the auspices of the National Nuclear Security Administration of the U.S. Department of Energy under Contract No. DE-AC52-06NA25396.
Funding AgencyGrant Number
Department of Energy (DOE)DE-AC52-06NA25396
Subject Keywords:Constraint programming; Graphical models; Power systems
Issue or Number:1
Record Number:CaltechAUTHORS:20161222-065548640
Persistent URL:
Official Citation:Dvijotham, K., Chertkov, M., Van Hentenryck, P. et al. Constraints (2017) 22: 24. doi:10.1007/s10601-016-9253-y
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:73119
Deposited By: Tony Diaz
Deposited On:22 Dec 2016 17:30
Last Modified:11 Nov 2021 05:11

Repository Staff Only: item control page