An Integer Programming Approach to the Multi-Level Bin Packing Problem with Partial Orders
C. Sağtürk (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
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.