Comparing approximate and optimal solution algorithms for the Multi-Level Bin Packing problem

Bachelor thesis (2022)

Authors

J.J. Groenheide Electrical Engineering, Mathematics and Computer Science

Contributors

M.G. Horn Algorithmics - EEMCS (mentor)
N. Yorke-Smith Algorithmics - EEMCS (mentor)
T.J. Viering Computer Science & Engineering-Teaching Team - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2022 Jeroen Groenheide
More Info
expand_more

Published Date

24-06-2022

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

Multi-Level variants of classic optimisation problems are becoming more noteworthy as the complexity of real life applications increases. In this research we investigate the Multi-Level Bin Packing optimisation problem, which models, for example, global logistics and part manufacturing. We will look at the performance of solving Integer Linear Programming formulations of the Multi-Level Bin Packing problem using IBM ILOG CPLEX Optimization Studio, and compare these results to the performance of simple heuristic-based algorithms to reach conclusions about the usefulness of optimal-solution algorithms for NP-Hard problems. We ultimately find that the simple heuristics leave a large gap in optimality, while the solving time for finding optimal solutions is still too large for practical instances. As such, we conclude that more specialised algorithms are needed that can balance the time cost and optimality, depending on the application.

Files

Final_Paper_Jeroen_Groenheide.... (pdf)
(pdf | 0.377 Mb)
Unknown license