Logic-Based Benders decomposition for transportation and manufacturing problems

Η παρούσα διατριβή εξετάζει την "Αποσύνθεση Logic-Based Benders'', μια σύγχρονη μέθοδο διαχωρισμού, προερχόμενη από την κλασσική Αποσύνθεση Benders. Καθώς ένα μεγάλης κλίμακας πρόβλημα βελτιστοποίησης δεν μπορεί να επιλυθεί απευθείας με τις τυπικές μεθόδους ακριβείας, είναι εύλογος ο διαχωρισμός του σε δύο υπομέρη, καθένα από τα οποία μπορεί να λυθεί βέλτιστα πιο εύκολα. Τα δύο υπομέρη ανταλλάσσουν γνώση επαναληπτικά, χρησιμοποιώντας γραμμικές ανισότητες που ονομάζονται ``Τομές Benders''. Η ευελιξία της μεθόδου μας επιτρέπει να διαχειριζόμαστε περίπλοκα προβλήματα μεγάλης κλίμακας, προερχόμενα από πραγματικά περιβάλλοντα μεταφοράς και βιομηχανίας. Με αφορμή τέτοιες περιπτώσεις, δείχνουμε διαφορετικές προσεγγίσεις της μεθόδου για να υπολογίσουμε σχεδόν βέλτιστες λύσεις σε εύλογο χρόνο για προβλήματα βιομηχανικής κλίμακας, δηλαδή για εκατοντάδες παραγγελίες προς παραγωγή ή παράδοση. Πέρα από την πρακτική συνεισφορά της διατριβής, που αποτελείται από τη συγκέντρωση αποδοτικών σχημάτων LBBD για τα υπό εξέταση προβλήματα, η τεχνική συνεισφορά αφορά τη δημιουργία έγκυρων και ισχυρών τομών Benders, που μπορούν να χρησιμοποιηθούν για γενικευμένες κατηγορίες προβλημάτων βελτιστοποίησης. Οι περιπτώσεις αυτές αφορούν προβλήματα ακέραιων μη δυαδικών μεταβλητών ή την απαλοιφή γειτονιών πολλαπλών λύσεων με χρήση μίας τομής, χωρίς απώλεια της βελτιστότητας. Κυριάρχο θέμα της διατριβής αποτελεί η εφαρμοσιμότητα της μεθόδου, όπως απδεικνύεται από την επιτυχημένη εφαρμογή της στα προβλήματα που παρουσιάζονται. Βασικό θέμα συζήτησης αποτελεί επίσης η περιγραφή του θεωρητικού υποβάθρου και της ανάπτυξης της μεθόδου κατά τις τελευταίες δεκαετίες, ξεκινώντας από τις βασικές αρχές του Ακέραιου Προγραμματισμού και καταλήγοντας στη σύγχρονη συναφή βιβλιογραφία. Τέλος, αναδεικνύονται υποσχόμενες προεκτάσεις, όπως η αξιοποίηση της μεθόδου για τη γραμμικοποίηση μη-γραμμικών προβλημάτων ή ως μηχανισμός επίλυσης στοχαστικών προβλημάτων, ως προοπτικές για μελλοντική έρευνα.