Résolution de problèmes d'optimisation pour les réseaux de transport d'électricité de grande taille avec des méthodes de programmation semi-définie positive

Le problème de l'Optimisation des Flux de Puissance (OPF) consiste à déterminer la puissance à produire pour satisfaire la demande électrique à moindre coût, tout en tenant compte des contraintes du réseau de transport d'électricité. La résolution de ce problème est aujourd'hui encore un défi, principalement car le problème est non convexe. Récemment, des méthodes d'optimisation globale prometteuses ont été proposées pour résoudre le problème de l'OPF. La plupart de ces méthodes reposent sur la Programmation Semi-Définie (SDP) car les relaxations SDP de l'OPF sont très précises voire exactes. Cependant, la résolution de problèmes SDP de grande taille est très coûteuse, ce qui limite la portée de ces méthodes d'optimisation globale. L'objectif principal de ce projet de recherche est d'accélérer la résolution des relaxations SDP de l'OPF afin de montrer que l'optimisation SDP reste un outil puissant pour l'OPF et ce, même pour des réseaux de grande taille. Pour atteindre cet objectif, nous commençons par concevoir des outils pour faciliter l'implémentation du problème de l'OPF et de ses nombreuses variantes. Nous cherchons ensuite à accélérer la résolution de la relaxation du rang de l'OPF en exploitant des méthodes de décomposition en cliques maximales. Nous proposons une nouvelle stratégie de fusion de cliques qui permet d'améliorer significativement le temps de résolution pour les instances MATPOWER. Nous proposons finalement une méthode d'énumération implicite s'appuyant sur une relaxation SDP pour résoudre différents problèmes d'OPF réactif (des problèmes d'OPF avec des variables binaires). Notre méthode permet de calculer la solution optimale ou au moins une bonne solution réalisable pour toutes les instances MATPOWER, y compris pour les plus gros réseaux. De plus, elle calcule de meilleures solutions qu'une heuristique d'arrondi, dans une limite de temps raisonnable et de manière robuste. Ainsi, nous montrons dans cette thèse qu'il est possible d'accélérer significativement la résolution de la relaxation du rang de l'OPF, la principale relaxation SDP utilisée dans le contexte de l'OPF. Nous démontrons aussi que l'optimisation SDP est un outil puissant pour résoudre des problèmes d'OPF réactif et cela même pour des réseaux de plus de 6000 nœuds.

Abstract

The Optimal Power Flow (OPF) is a famous power system optimization problem. It consists in computing an optimal power generation dispatch for an alternating current transmission network that respects power flow equations and operational constraints. The OPF problem is highly nonconvex and there is still no efficient method to solve this problem to global optimality. Nevertheless, promising methods have been proposed recently. Most of them are based on Semidefinite Programming (SDP) since semidefinite relaxations of OPF problems are tight. However, the resolution of semidefinite relaxations is very costly, especially for large-scale networks. Therefore, all promising methods depend on large-scale SDP problems being solved efficiently. The main objective of this research project is to decrease the resolution time of semidefinite relaxations of OPF problems to demonstrate that semidefinite relaxations are still powerful to solve OPF problems, even for large-scale networks. To reach this objective, we first conceive programming tools to facilitate the implementation of the OPF problem and its variants. We then seek to speed up the resolution of the rank relaxation for OPF problems thanks to clique decomposition techniques. We propose a new strategy of clique merging which significantly improves the solving time for MATPOWER instances. We finally propose a SDP-based Branch-and-Bound algorithm to solve several Reactive OPF problems that contain binary variables. Our algorithm computes the optimal solution or at least a good feasible solution for all MATPOWER instances, including for large-scale networks. Moreover, it computes better solutions than a rounding heuristic and it is also more robust. Thus, we show in this thesis that it is possible to significantly speed up the resolution of the rank relaxation of the OPF problem, which is the main SDP relaxation used to solve OPF problems. We also demonstrate that semidefinite programming is a powerful tool to solve Reactive Optimal Power Flow problems, even for networks with more than 6000 buses.