Where: University of Montpellier or University Sorbonne Paris Nord (both in France), according to the candidate’s preference
When: The position remains open until it is filled
- Project description
- The Optimal Power Flow (OPF) problem [1] involves determining a generation dispatch that meets electricity demand and satisfies transmission network constraints while minimizing generation costs. Solving OPF instances to global optimality is a challenge since it is highly nonconvex and NP-hard [2]. Most of the promising exact methods proposed are based on Semidefinite Programming (SDP) [3] as SDP relaxations provide tight lower bounds for OPF problems. However, these methods may not scale well as solving large SDP problems is costly. Thus, it is crucial to accelerate the resolution of SDP relaxations for OPF problems to make progress towards global optimality. One promising approach for solving these relaxations is to apply clique decomposition techniques [4]. Their effectiveness depends on the ability to identify the structure in the power system and determine the best decomposition accordingly. There are many admissible clique decompositions for the same SDP relaxation, and these decompositions are not equivalent in terms of their impact on solution time. Therefore, it is critical to identify what characterizes ”good” decompositions, i.e., decompositions that significantly reduce the computation time of the associated relaxation. Unfortunately, currently, all the algorithms proposed in the literature to find a ”good” decomposition are guided by general rules and principles [5]. We propose using deep learning algorithms to learn what constitutes a good decomposition. More formally, for a given OPF instance and associated clique decomposition, we aim to predict whether the use of the decomposition will allow us to solve the SDP relaxation more quickly (and if so, by how much). A key aspect of this application is that each instance can be represented as a graph. From a methodological perspective, it is essential to use techniques that effectively encode a graph-based instance. Among the many possible options, we propose using Graph Neural Networks (GNNs) [6]. The intriguing idea behind GNNs is to learn the common local and global structural patterns of graphs through designed convolution and readout functions. Using GNNs is particularly challenging in our case because it is necessary to encode two graphs: one associated with the instance and another associated with the clique decomposition.
References- [1] J. Carpentier, “Contribution to the economic dispatch problem,” Bulletin de la Societe Francaise des Electriciens, vol. 3, no. 8, pp. 431–447, 1962.
- [2] D. Bienstock and A. Verma, “Strong np-hardness of ac power flows feasibility,” Operations Research Letters, 2019.
- [3] A. Gopalakrishnan, A. U. Raghunathan, D. Nikovski, and L. T. Biegler, “Global optimization of optimal power flow using a branch & bound algorithm,” in 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 609–616, IEEE, 2012.
- [4] L. Vandenberghe, M. S. Andersen, et al., “Chordal graphs and semidefinite optimization,” Foundations and Trends in Optimization, vol. 1, no. 4, pp. 241–433, 2015.
- [5] J. Sliwak, E. D. Andersen, M. F. Anjos, L. L ́etocart, and E. Traversi, “A clique merging algorithm to solve semidefinite relaxations of optimal power flow problems,” IEEE Transactions on Power Systems, vol. 36, no. 2, pp. 1641–1644, 2021.
- [6] S. Zhang, H. Tong, J. Xu, and R. Maciejewski, “Graph convolutional networks: Algorithms, applications and open challenges,” in International Conference on Computational Social Networks, pp. 79–91, Springer, 2018.
- The Optimal Power Flow (OPF) problem [1] involves determining a generation dispatch that meets electricity demand and satisfies transmission network constraints while minimizing generation costs. Solving OPF instances to global optimality is a challenge since it is highly nonconvex and NP-hard [2]. Most of the promising exact methods proposed are based on Semidefinite Programming (SDP) [3] as SDP relaxations provide tight lower bounds for OPF problems. However, these methods may not scale well as solving large SDP problems is costly. Thus, it is crucial to accelerate the resolution of SDP relaxations for OPF problems to make progress towards global optimality. One promising approach for solving these relaxations is to apply clique decomposition techniques [4]. Their effectiveness depends on the ability to identify the structure in the power system and determine the best decomposition accordingly. There are many admissible clique decompositions for the same SDP relaxation, and these decompositions are not equivalent in terms of their impact on solution time. Therefore, it is critical to identify what characterizes ”good” decompositions, i.e., decompositions that significantly reduce the computation time of the associated relaxation. Unfortunately, currently, all the algorithms proposed in the literature to find a ”good” decomposition are guided by general rules and principles [5]. We propose using deep learning algorithms to learn what constitutes a good decomposition. More formally, for a given OPF instance and associated clique decomposition, we aim to predict whether the use of the decomposition will allow us to solve the SDP relaxation more quickly (and if so, by how much). A key aspect of this application is that each instance can be represented as a graph. From a methodological perspective, it is essential to use techniques that effectively encode a graph-based instance. Among the many possible options, we propose using Graph Neural Networks (GNNs) [6]. The intriguing idea behind GNNs is to learn the common local and global structural patterns of graphs through designed convolution and readout functions. Using GNNs is particularly challenging in our case because it is necessary to encode two graphs: one associated with the instance and another associated with the clique decomposition.
- Candidate Requirements
- To be considered for the position to work on this project, candidates should meet the following requirements:
- Candidates should have a Ph.D in Optimization, Machine Learning or a related field. A solid understanding of mathematical concepts, particularly in optimization, linear algebra, and graph theory, is essential for this role. Candidates should be comfortable working with mathematical models and algorithms.
- Experience or knowledge in machine learning and deep learning techniques, especially as applied to graph-based data, is highly desirable. Familiarity with Graph Neural Networks (GNNs) is a significant advantage.
- Candidates must possess strong programming skills, with proficiency in relevant languages and tools such as Python,
Julia or C++. Familiarity with software for solving optimization problems, like SDP solvers, is a plus.
- To be considered for the position to work on this project, candidates should meet the following requirements:
- Supervisors and contacts
- Emiliano TRAVERSI. Université de Montpeller, France: emiliano.traversi@gmail.com
- Miguel Anjos: Miguel.F.Anjos@ed.ac.uk
- Pegah ALIZADEH. Ericsson R&D center, Paris, France: pegah.alizadeh@gmail.com
- Lucas Létocart: letocart@lipn.univ-paris13.fr