Αλγόριθμοι διεπίπεδου προγραμματισμού για βέλτιστη υποβολή προσφορών παραγωγών ενέργειας σε αγορές ημερήσιου προγραμματισμού ηλεκτρικής ενέργειας

Abstract

In this dissertation, we consider the problem of devising optimal price-offers for an energy producer participating in a day-ahead electricity market which exhibits non-convexities due to the discrete nature of the generation units’ commitments, assuming perfect knowledge of the technical characteristics and bids of all remaining producers. The problem is formulated as a bilevel optimization model with linear constraint sets. The producer acts as the upper-level decision maker, maximizing his individual profit upon clearing of the market, while an independent system operator acts as the lower-level decision maker clearing of the market. The use of discrete variables prohibits the application of typical methodologies for finding its optimal solution. We consider the single period variant of the problem first, and we develop an exact algorithm for its solution, utilizing important findings from the theory of integer parametric programming. Next, we develop a heuristic and an exact solution methodology for tackling the multi-period variant of the problem. We go on to develop an improved version of the exact solution algorithm for the treatment of the multi-period variant of the problem. Including special optimality conditions ensuring that the energy quantity distribution in each time period of the planning horizon is optimal for the corresponding set of producers that has been identified as active in that time period, the solution of the original problem to global optimality becomes equivalent to identifying the optimal set of active producers in each time period of the planning horizon. We present experimental results for every algorithmic approach, which describe the ability of each algorithm to handle the problem, the computational requirements as well as the size of the problems that can be solved in each case. For the development of the proposed optimization models and the specialized solution methodologies, we utilized the C/C++ programming language, and the solution of the proposed optimization models was obtained using the commercial optimization solvers as LINGO. The significance of the present research contribution becomes evident when one considers the lack of generic solution methodologies for bilevel optimization models such as the one under consideration.

Στην παρούσα διδακτορική διατριβή, εξετάζουμε το πρόβλημα σχεδιασμού βέλτιστων τιμών-προσφορών για έναν παραγωγό ενέργειας που συμμετέχει σε μια αγορά ημερήσιου προγραμματισμού ηλεκτρικής ενέργειας, η οποία περιλαμβάνει μη κυρτότητες λόγω της διακριτής φύσης των δεσμεύσεων των μονάδων παραγωγής, υποθέτοντας πλήρη γνώση των τεχνικών χαρακτηριστικών και των προσφορών των υπόλοιπων παραγωγών. Το πρόβλημα μορφοποιείται ως διεπίπεδο μοντέλο βελτιστοποίησης με γραμμικούς περιορισμούς. Ο παραγωγός ενεργεί ως υπεύθυνος λήψης αποφάσεων στο άνω επίπεδο μεγιστοποιώντας το ατομικό του κέρδος μετά την εκκαθάριση της αγοράς, ενώ ένας ανεξάρτητος διαχειριστής συστήματος ενεργεί ως υπεύθυνος στο κάτω επίπεδο εκκαθαρίζοντας την αγορά. Η χρήση διακριτών μεταβλητών απαγορεύει την εφαρμογή τυπικών μεθοδολογιών για την εύρεση της βέλτιστης λύσης. Πρώτα εξετάζουμε την εκδοχή μιας περιόδου του προβλήματος και αναπτύσσουμε έναν ακριβή αλγόριθμο για την επίλυσή του, χρησιμοποιώντας σημαντικά αποτελέσματα από τη θεωρία του ακέραιου παραμετρικού προγραμματισμού. Στη συνέχεια, αναπτύσσουμε μια ευρετική και μια ακριβή αλγοριθμική μεθοδολογία επίλυσης για την αντιμετώπισή της εκδοχής πολλαπλών περιόδων του προβλήματος. Συνεχίζουμε αναπτύσσοντας μία βελτιωμένη έκδοση του ακριβούς αλγόριθμου επίλυσης για την αντιμετώπιση της εκδοχής πολλαπλών περιόδων του προβλήματος. Ενσωματώνοντας ειδικές συνθήκες βελτιστότητας οι οποίες διασφαλίζουν ότι η κατανομή της ποσότητας της ενέργειας σε κάθε χρονική περίοδο του ορίζοντα προγραμματισμού είναι η βέλτιστη για το αντίστοιχο σύνολο παραγωγών που έχουν αναγνωριστεί ως ενεργοί κατά τη συγκεκριμένη χρονική περίοδο, η εύρεση της ολικά βέλτιστης λύσης του αρχικού προβλήματος ισοδυναμεί με τον προσδιορισμό του βέλτιστου συνόλου ενεργών παραγωγών σε κάθε χρονική περίοδο του ορίζοντα προγραμματισμού. Παρουσιάζουμε πειραματικά αποτελέσματα για κάθε αλγοριθμική προσέγγιση, τα οποία περιγράφουν την ικανότητα κάθε αλγόριθμου να χειριστεί το πρόβλημα, τους υπολογιστικούς πόρους που απαιτεί καθώς και το μέγεθος τον προβλημάτων που μπορούν να επιλυθούν σε κάθε περίπτωση. Για την ανάπτυξη των προτεινόμενων μοντέλων βελτιστοποίησης και των εξειδικευμένων μεθοδολογιών επίλυσης, χρησιμοποιήσαμε τη γλώσσα προγραμματισμού C/ C++ και η λύση των προτεινόμενων μοντέλων βελτιστοποίησης ελήφθη χρησιμοποιώντας εμπορικά λογισμικά βελτιστοποίησης όπως το LINGO. Η σημαντικότητα της συνεισφοράς της παρούσας έρευνας καταδεικνύεται εάν κάποιος λάβει υπόψη την έλλειψη γενικών μεθοδολογιών επίλυσης για διεπίπεδα μοντέλα βελτιστοποίησης, όπως αυτά που εξετάζονται.