Acceleration of benders decomposition method for the solution of mixed integer linear programming problems
Authors: Φραγκογιός Αντώνιος 
Published: July 2024

Στην παρούσα διδακτορική διατριβή μελετάται η μέθοδος μαθηματικής αποσύνθεσης Benders για την επίλυση Προβλημάτων Μικτού Ακέραιου Γραμμικού Προγραμματισμού (ΜΑΓΠ) και εισάγονται τέσσερις νέες τεχνικές για την επιτάχυνσή της. Δύο από αυτές τις τεχνικές αφορούν συγκεκριμένα προβλήματα, ενώ οι άλλες δύο είναι γενικευμένες και μπορούν να εφαρμοστούν σε οποιοδήποτε πρόβλημα. Η πρώτη τεχνική είναι γενικευμένη και αντιμετωπίζει την περίπτωση όπου η εφαρμογή της μεθόδου αποσύνθεσης Benders σε ένα πρόβλημα ΜΑΓΠ οδηγεί σε ένα υποπρόβλημα που περιλαμβάνει ακέραιες μεταβλητές. Σε αυτήν την περίπτωση, δεν είναι δυνατή η εφαρμογή του κλασικού αλγορίθμου Benders και, για το λόγο αυτό, προτείνεται ένας αλγόριθμος Branch-and-Cut. Οι περιορισμοί ακεραιότητας του υποπροβλήματος χαλαρώνουν και ο αλγόριθμος Benders εφαρμόζεται σε ένα πλαίσιο Branch-and-Bound. Οι τομές Benders που δημιουργούνται σε έναν κόμβο του δέντρου Branch-and-Bound αποδεικνύεται ότι είναι έγκυρες για όλους τους απόγονους κόμβους. Αυτές οι τομές, που αναφέρονται ως «Τοπικές Τομές», μπορούν να χρησιμοποιηθούν στην αρχικοποίηση του κύριου προβλήματος κάθε απόγονου κόμβου, οδηγώντας έτσι σε καλύτερα αρχικά όρια. Επιπλέον, παρουσιάζεται ένας καινοτόμος τρόπος για τον ορισμό των «Τοπικών Τομών» σε μια γενική μορφή («Γενικευμένες / Καθολικές Τομές»), προσφέροντας τη δυνατότητα επαναχρησιμοποίησής τους σε ολόκληρο το δέντρο Branch-and-Bound. Ο προτεινόμενος αλγορίθμος εφαρμόζεται στο κλασικό Πρόβλημα Capacitated Fixed Charge Multiple Knapsack (CFCMK) και προσφέρει σημαντική μείωση του υπολογιστικού χρόνου σε σύγκριση με τον αντίστοιχο αλγόριθμο χωρίς «Τοπικές Τομές». Η δεύτερη τεχνική αφορά το Πρόβλημα Τοποθεσιών Μέγιστης Κάλυψης (ΠΤΜΚ). Συγκεκριμένα, προτείνεται ένα Μοντέλο Double-type Double-standard (DtDsM), με εφαρμογή στον προσδιορισμό της βέλτιστης τοποθεσίας των δημόσιων υπηρεσιών έκτακτης ανάγκης (π.χ. ασθενοφόρα, πυροσβεστικά και αστυνομικά οχήματα). Στο DtDsM εξετάζονται δύο τύποι οχημάτων: τα κανονικά και τα εφεδρικά οχήματα. Τα κανονικά οχήματα προσφέρουν πλήρη εξυπηρέτηση, αλλά έχουν μικρή απόσταση κάλυψης σε προκαθορισμένο χρόνο, ενώ τα εφεδρικά έχουν μεγαλύτερη απόσταση κάλυψης, αλλά προσφέρουν μόνο μια βασική εξυπηρέτηση. Κάθε σημείο ζήτησης πρέπει να βρίσκεται εντός της απόστασης κάλυψης ενός εφεδρικού οχήματος, εάν δεν βρίσκεται εντός της απόστασης κάλυψης ενός κανονικού οχήματος, διασφαλίζοντας ότι λαμβάνει τις ελάχιστες βασικές υπηρεσίες. Για τη λύση του DtDsM για το ΠΤΜΚ προτείνεται ένας επιταχυνόμενος αλγόριθμος αποσύνθεσης Benders, βασισμένος στην αξιοποίηση της ειδικής δομής του προβλήματος. Ο προτεινόμενος αλγόριθμος ξεπερνά τόσο το εμπορικό λογισμικό βελτιστοποίησης CPLEX όσο και τον κλασικό αλγόριθμο Benders, αναφορικά με την ταχύτητα και την ακρίβεια. Η τρίτη τεχνική είναι μια γενικευμένη, που στοχεύει στην παραγωγή πιο αποτελεσματικών τομών εφικτότητας και βελτιστότητας Benders, προκειμένου να μειωθεί η διακύμανση του ορίου και να επιταχυνθεί ο αλγόριθμος. Το κύριο πλεονέκτημα της προτεινόμενης τεχνικής είναι ότι μπορεί να χρησιμοποιηθεί εύκολα σε κάθε πρόβλημα του Μαθηματικού Προγραμματισμού, όπου εφαρμόζεται η αποσύνθεση Benders, χωρίς κανέναν περιορισμό. Τέσσερις διαφορετικές παραλλαγές του προτεινόμενου αλγορίθμου εφαρμόζονται σε ένα Μαθηματικό Μοντέλο Προγραμματισμού Μεταφοράς Αργού Πετρελαίου και προκύπτουν υποσχόμενα αποτελέσματα από υπολογιστικής άποψης. Τέλος, η τέταρτη τεχνική αφορά το Πρόβλημα Δρομολόγησης Οχημάτων με Πολλαπλές Διαδρομές, Ταχύτητα Εξαρτώμενη από το Χρόνο και Χρονικά Παράθυρα, το οποίο είναι ένα δύσκολο πρόβλημα που αντιμετωπίζουν καθημερινά οι εταιρείες logistics που δραστηριοποιούνται στα αστικά κέντρα. Συγκεκριμένα, προτείνεται μια αναδιαμόρφωση ενός μοντέλου της βιβλιογραφίας, με σκοπό τη μείωση του μεγέθους του. Στην εν λόγω αναδιαμόρφωση εφαρμόζεται η μέθοδος αποσύνθεσης Benders με αποτελεσματικό τρόπο, με αποτέλεσμα το υποπρόβλημα που προκύπτει να μην έχει χάσμα δυϊκότητας. Με την αξιοποίηση των ιδιαίτερων χαρακτηριστικών του προβλήματος, εισάγονται αρκετές νέες έγκυρες ανισώσεις, προκειμένου να περιοριστεί το χαλαρό κύριο πρόβλημα και να επιτευχθούν λιγότερες μη εφικτές λύσεις και καλύτερα κατώτερα όρια. Για τη λύση του προβλήματος, προτείνεται ένας καινοτόμος αλγόριθμος που περιλαμβάνει υποβέλτιστες κύριες λύσεις και μια διαδικασία παραγωγής πολλαπλών τομών, η οποία βασίζεται στην προσεκτική παρατήρηση των τιμών των μεταβλητών του δυϊκού υποπροβλήματος Benders. Δύο παραλλαγές του προτεινόμενου επιταχυνόμενου αλγορίθμου αποσύνθεσης Benders εφαρμόζονται σε δεδομένα συγκριτικής αξιολόγησης και εμφανίζουν βελτιωμένη απόδοση και ισχυρότερα όρια από τα μη αποσυντιθέμενα μοντέλα.