Back to search

Athens University Economics and Business (AUEB)

Logic-Based Benders decomposition for transportation and manufacturing problems

Abstract

dc:description

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.

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

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/55805

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Avgerinos, Ioannis; Αυγερινός, Ιωάννης. Logic-Based Benders decomposition for transportation and manufacturing problems. Athens University Economics and Business (AUEB), 2024. http://hdl.handle.net/10442/hedi/55805