AUEB Library - Digital Repository

PYXIDA Institutional Repository
and Digital Library

Username
Password

Collections :	Ιδρυματικό Αποθετήριο ΟΠΑ / AUEB Institutional Repository Σχολή Διοίκησης Επιχειρήσεων / School of Business Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας / Department of Management Science and Technology Διδακτορικές διατριβές / PhD Theses

Title :	Logic-based Benders decomposition for transportation and manufacturing problems

Alternative Title :	Αποσύνθεση Logic-based Benders για προβλήματα μεταφοράς και βιομηχανίας

Creator :	Αυγερινός, Ιωάννης Avgerinos, Ioannis

Contributor :	Mourtos, Ioannis (Επιβλέπων καθηγητής) Kritikos, Emmanouil (Εξεταστής) Androutsopoulos, Konstantinos (Εξεταστής) Giannikos, Ioannis (Εξεταστής) Emiris, Dimitrios (Εξεταστής) Kaparis, Konstantinos (Εξεταστής) Papavasiliou, Anthony (Εξεταστής) Athens University of Economics and Business, Department of Management Science and Technology (Degree granting institution)

Contributor :

Mourtos, Ioannis (Επιβλέπων καθηγητής)
Kritikos, Emmanouil (Εξεταστής)
Androutsopoulos, Konstantinos (Εξεταστής)
Giannikos, Ioannis (Εξεταστής)
Emiris, Dimitrios (Εξεταστής)
Kaparis, Konstantinos (Εξεταστής)
Papavasiliou, Anthony (Εξεταστής)
Athens University of Economics and Business, Department of Management Science and Technology (Degree granting institution)

Type :	Text

Extent :	133p.

Language :	en

Identifier :	http://www.pyxida.aueb.gr/index.php?op=view_object&object_id=10978

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.

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.

Subject :	Μέθοδοι αποσύνθεσης Αποσύνθεση Logic-based Benders Ακέραιος προγραμματισμός Partitioning methods Logic-based Benders decomposition Integer programming

Date Available :	2024-01-26 13:26:56

Date Issued :	23-01-2024

Date Submitted :	2024-01-26 13:26:56

Access Rights :	Free access

Licence :

File: Avgerinos_2024.pdf

Type: application/pdf

Login