A Comparative Study of Approaches to the Single Container Loading Problem

This paper presents and compares two approaches to the single-container loading problem (SCLP). This problem seeks to a subset of items (i.e., boxes) of maximum value that can be packed in a three-dimensional container. The approaches developed for the SCLP are iterative and each iteration consists of solving integer programming and constraint programming models, where the models are solved with the CPLEX optimizer. In the first approach, it is used a model for the one-dimensional knapsack problem and a constraint programming model. In the second approach, it is used the two models of the first approach and a relaxation based on the two-dimensional knapsack problem. In order to compare the performance of the two approaches, experiments are carried out with instances of the literature. The approaches found an optimal solution for 50% of the instances. For the other 50%, they achieved an upper bound for the optimal value solution. In addition, the results showed that the first approach was faster than the second approach, although the second approach succeeded in proving the infeasibility of more subsets than the first approach in the instances for which the optimal solution could not be achieved. The test of statistical significance performed showed that there is difference between the runtimes of the two approaches. Index Terms - Single-Container Loading Problem, Constraint Programming, Integer Programming, Packing Problems.