Logic-based Benders decomposition for transportation and manufacturing problems

Abstract

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

This thesis examines the Logic-Based Benders Decomposition, a modern partitioning method, originating from the classic Benders Decomposition, which is known since the 1960's. As {a large optimisation problem} cannot be {solved directly} by regular exact methods, {it is reasonable to partition it} into two counterparts, each {being} more easily solved to optimality. The {two} counterparts exchange knowledge in an iterative manner, {through} linear inequalities called Benders cuts.The flexibility of the method allows us to address {elaborate} problems {of large scale}, derived from real transportation and manufacturing environments. Motivated by such cases, we show different approaches of the method to provide {near-optimal solutions} in reasonable time for problems of industrial scale, i.e., for hundreds of orders to manufacture or deliver. Beyond the practical contribution of the thesis, which is the consolidation of efficient LBBD schemes for the {problems examined}, {its} technical contribution {concerns} the construction of generators of valid strong Benders cuts, which can be legitimately utilised on generic classes of optimisation problems. {These include} the construction of cuts for non-binary integer variables or the elimination of neighbourhoods of multiple solutions with a single inequality without loss of optimality.The applicability of the method, as proved by its successful implementation on the presented problems, occupies most of the structure of the thesis. {To reach that}, the theoretical framework and the development of the method through the last decades, starting from the fundamentals of Integer Programming and ending {at recent relevant} literature, {is also a major subject} in discussion. To conclude, promising extensions, such as {the use of the method} as a linearisation technique for nonlinear problems or as a mechanism for solving stochastic problems are brought forward to highlight {its extendability along with} its prospects for future research.