Athens University Economics and Business (AUEB)
Logic-Based Benders decomposition for transportation and manufacturing problems
Abstract
dc:descriptionThis 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.
Degree
thesis:*- Grantor dc:publisher
- Athens University Economics and Business (AUEB)
- Year dc:date
- 2024
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Avgerinos, Ioannis
- Αυγερινός, Ιωάννης
Subjects
dc:subject × 12- Μέθοδοι αποσύνθεσης
- Αποσύνθεση Logic-Based Benders
- Ακέραιος προγραμματισμός
- Partitioning methods
- Logic-Based Benders decomposition
- Integer programming
- Άλλες Επιστήμες Μηχανικού και Τεχνολογίες
- Επιστήμες Μηχανικού και Τεχνολογία
- Μηχανική και Τεχνολογίες, άλλοι τομείς
- Other Engineering and Technologies
- Engineering and Technology
- Engineering and Technologies, miscellaneous
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/55805