Ανάπτυξη Μεθοδολογίας Εκτίμησης Ελαχίστων Σημείων του Εύρους Αντικειμενικών Συναρτήσεων σε Προβλήματα Πολυστοχικού Προγραμματισμού υπό Αβεβαιότητα

Abstract

Ο πολυστοχικός προγραμματισμός είναι αρκετά διαδεδομένος στον τομέα της ενέργειας και πραγματοποιούνται διαρκώς μελέτες για την ανάπτυξη μεθόδων για την επίλυση τέτοιου τύπου προβλημάτων. Από την πληθώρα αυτών εστιάζουμε στην οικογένεια μεθόδων AUGMECON και συγκεκριμένα στην AUGMECON-Py. Η AUGMECON-Py διακριτοποιεί τον χώρο εφικτών λύσεων κάθε αντικειμενικής συνάρτησης και βρίσκει τις κατά Pareto βέλτιστες λύσεις με αρκετά αποδοτικό τρόπο. Ωστόσο, επειδή εκφράζονται όλες οι αντικειμενικές συναρτήσεις εκτός από μία ως περιορισμοί του πολυστοχικού προβλήματος μπορεί η αλλαγή της θέσης τους στο πρόβλημα, να επηρεάσει τον χρόνο εκτέλεσης του αλγορίθμου και τον αριθμό των βέλτιστων κατά Pareto λύσεων που θα βρεθούν. Τα παραπάνω επηρεάζονται καθοριστικά και από την εκτίμηση των ελαχίστων τιμών -για τις οποίες υπάρχει αβεβαιότητα- κάθε αντικειμενικής συνάρτησης καθώς το εύρος του χώρου εφικτών λύσεών τους θα αλλάζει. Τα σημεία ναδίρ μέχρι στιγμής εκτιμούνται πολλαπλασιάζοντας με έναν συντελεστή τις ελάχιστες τιμές κάθε αντικειμενικής συνάρτησης έπειτα από την λεξικογραφική βελτιστοποίησή τους, τον “nadir_cutoff". Ιδανικά οι εκτιμώμενες τιμές των σημείων ναδίρ θα πρέπει να είναι μικρότερες ή ίσες από τις πραγματικές έτσι ώστε να μην χαθεί καμία βέλτιστη λύση. Η πρόκληση έγκειται στην εύρεση ενός συντελεστή που θα είναι αρκετά μικρός ώστε να περιλαμβάνονται όλες οι λύσεις αλλά όχι τόσο ώστε να αυξάνεται σημαντικά ο χρόνος εκτέλεσης του προγράμματος. Στην παρούσα εργασία ορίζεται μια μεθοδολογία αποτελεσματικής εκτίμησης του συντελεστή nadir_cutoff που ονομάστηκε 2-Stage AUGMECON-Py και έπειτα εφαρμόζεται σε ενεργειακά προβλήματα εύρεσης βέλτιστων χαρτοφυλακίων χρηματοδότησης τεχνολογιών χαμηλών εκπομπών με πραγματικά δεδομένα. Η νέα μέθοδος χρησιμοποιεί μέρος των δεδομένων του προβλήματος για να εκτιμήσει τον συντελεστής nadir_cutoff με αρκετά μεγάλη ακρίβεια. Η μέθοδος αυτή ελαχιστοποιεί την πιθανότητα απώλειας λύσεων και διαθέτει σημαντικά χρονικά πλεονεκτήματα ιδιαίτερα όταν γίνεται ανάλυση Monte Carlo του προβλήματος.