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.