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.

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.

This paper introduces and studies the Multi-Level Bin Packing Problem with Time Windows. This is a NP-hard problem with real-world applications in logistics. This problem states that items with certain sizes need to be packed inside bins without exceeding their capacity. These bins then again need to be assigned to other bins while minimizing the cost of the used bins. At the same time, each item has a time interval and there must be a common time point between all the items that are packed in the same bin that should be as early as possible. Not much research has been done regarding this problem. In this paper, we suggest multiple models that can be solved using Integer Programming and compare their performance. The results show slight differences in performance between the models.

The Multi-Level Bin Packing problem is a generalisation of the widely-known NP-hard Bin Packing problem. This work aims to investigate approaching this problem, as well as a version including Class Constraints, through integer programming. By modelling the problems in two ways: standard, and with a network flow approach. The studying of the performance of these formulations on various instances, provides a greater insight into the possibilities of integer programming for this purpose. Furthermore, evaluating the two approaches gives an initial suggestion for developing effective models for solving the aforementioned problems.

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.