ALGORITHMS FOR THE LARGE-SCALE UNIT COMMITMENT PROBLEM IN THE SIMULATION OF POWER SYSTEMS

The Unit Commitment Problem (UCP) is a mathematical programming problem where a set of power plants needs to be scheduled to satisfy energy demand and other system-wide constraints. It has been employed for decades to support short-term operational planning of power plants. In this work we tackle the problem of solving large-scale linear UCPs to perform accurate medium-term power systems simulations, with the additional requirements of employing conventional computing power, such as personal computers, and a solution time of a few hours. The problem, under such conditions, is routinely faced by our industry partner, the Energy Systems Development department at RSE S.p.A. (Ricerche Sistema Energetico), a major industrial research centre on power systems in Italy. The direct optimization of these formulations via general-purpose solvers is impractical. While good heuristic solutions, that is with an optimality gap below 10%, can be found for large-scale UCPs in affordable time, more accurate solutions, for example with a gap below 1%, are sought to improve the reliability of the simulations and help domain experts, who may not be familiar with the details of mathematical programming methods, to better support their analysis. Among the ideas we explored, the following methods are the most promising: a matheuristic to efficiently compute good solutions and two exact bounding methods: column generation and Benders decomposition. These methods decompose the problem by decoupling the commitment of thermal plants, represented by discrete variables, and their level of production, represented by continuous variables. Our experiments proved that the model posses inherent properties as degeneracy and objective flatness which hinder or prevent convergence in state-of-the-art solvers. On the other hand, the methods we devised, by effectively exploiting structural properties of the model, allow to reach quasi-optimal solutions within a few iterations on most instances.

Lo Unit Commitment Problem (UCP) è un problema di programmazione matematica dove un insieme di impianti termoelettrici deve essere programmato per soddisfare la domanda di energia e altri vincoli di sistema. Il modello è impiegato da decenni per supportare la pianificazione operazionale di breve termine dei sistemi elettrici. In questo lavoro affrontiamo il problema di risolvere UCP lineari di larga-scala per realizzare simulazioni accurate di sistemi elettrici, con i requisiti aggiuntivi di impiegare capacità di calcolo convenzionali, ad esempio i personal computers, ed un tempo di soluzione di poche ore. Il problema, sotto le medesime condizioni, è affrontato abitualmente dal nostro partner industriale RSE S.p.A. (Ricerche Sistema Energetico), uno dei principali centri ricerche industriali su sistemi energetici in Italia. L’ottimizzazione diretta di queste formulazioni con solutori generici è impraticabile. Nonostante sia possibile calcolare buone soluzioni euristiche, ovvero con un gap di ottimalità sotto il 10%, in tempi ragionevoli per UCP di larga scala, si richiedono soluzioni più accurate, per esempio con gap sotto l’1%, per migliorare l’affidabilità delle simulazioni ed aiutare gli esperti di dominio, che potrebbero non essere familiari con i dettagli dei metodi di programmazione matematica, a supportare meglio le loro analisi. Tra le idee che abbiamo esplorato i seguenti metodi risultano i più promettenti: una mateuristica per calcolare efficientemente buone soluzioni e due metodi esatti di bounding: column generation e Benders decomposition. Questi metodi decompongono il problema disaccoppiando il commitment degli impianti termoelettrici, rappresentati da variabili discrete, e il loro livello di produzione, rappresentato da variabili continue. I nostri esperimenti dimostrano che il modello possiede proprietà intrinseche come degenerazione e forma della funzione obbiettivo piatta che ostacolano o impediscono la convergenza in risolutori allo stato dell’arte. Tuttavia, i metodi che abbiamo sviluppato, sfruttando efficacemente le proprietà strutturali del modello, permettono di raggiungere soluzioni quasi ottime in poche iterazioni per la maggior parte delle istanze.