Solving Integer Programming Models for the Multi-Level Bin Packing Problem with Conflict Constraints
J.M. Tokarz (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Matthias 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 and its variants are some of the most popular combinatorial optimization problems. They have a wide range of real-life applications yet, they are some of the harder problems we know of. In this paper we solve the Multi-Level Bin Packing Problem and a variant of it, Multi-Level Bin Packing Problem with Conflict Constraints, using Integer Programming. We propose two Integer Programming models, a standard one and one with additional flow optimizations. We hypothesized that the second model will have a smaller solution space and consequently an improved performance for both of the problems. However, we find that the second model’s performance is worse and that although it may have a smaller solution space, the comparison of the BnB nodes points towards inconclusiveness.