An Integer Programming Approach to the Multi-Level Bin Packing Problem with Partial Orders

Bachelor thesis (2022)

Authors

C. Sağtürk 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 Can Sağtürk
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

The multi-level bin packing problem (MLBP) and its variant problem with partial orders (MLBPPO) are NP-Hard problems that can be applied in a logistical setting to improve efficiency in packing. However, despite their possible use cases, there is little to no literature on how to solve these problems in a reasonable amount of time. In this work, we propose two Integer Programming (IP) models for each problem, one of which is an adaptation from an already existing bin packing implementation, and another with network flow constraints for stronger LP relaxations. The comprehensive experimentation conducted on varying sizes of problem instances suggests that the presented models for the MLBP are highly effective at solving instances with up to 50 items and 5 levels, while neither of the models outperforms the other decisively. For the MLBPPO, the model based on the BP implementation is potent at solving up to 20 items and 5 levels depending on the number of partial orders, while the network flow model cannot compete.

Files

CSagturk_Research_Paper.pdf
(pdf | 0.41 Mb)
Unknown license