Lazy Clause Generation for Bin Packing

Abstract

In this paper we embed a solution for bin packing problems in a constraint programming environment.
Existing solutions for bin packing problems are plentiful, but rigid.
We have taken existing solutions of bin packing in constraint programming, and analysed the steps this algorithm takes.
We then developed explanations for these steps in the form of boolean clauses.
Using these explanations, a constraint programming paradigm by the name of lazy clause generation is able to generate new rules, that prevent the solver from making the same mistake twice.
We have compared our implementation to two different solutions.
Firstly we compared it to a decomposition, where the bin packing constraint was broken down into many smaller and simpler constraints.
Secondly, we compared our implementation to a version with naive explanations.
In one benchmark, comparing our version to the decomposition in a pure bin packing problem, our implementation vastly outperformed the decomposition.
In other benchmarks, the results comparing our version to the other two were much more inconclusive.
While showing marginal improvements in some cases, our version performed worse in other cases.
The research performed in this paper definitely shows promise, and there is merit in exploring this approach in further research.