Comparing approximate and optimal solution algorithms for the Multi-Level Bin Packing problem
J.J. Groenheide (TU Delft - Electrical Engineering, Mathematics and Computer Science)
M.G. Horn – Mentor (TU Delft - Algorithmics)
Neil Yorke-Smith – Mentor (TU Delft - Algorithmics)
Tom Viering – Graduation committee member (TU Delft - Computer Science & Engineering-Teaching Team)
More Info
expand_more
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.
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.