Lazy Clause Generation for Bin Packing
Explaining Bin Packing Propagation with Boolean Variables
M. de Kloe (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Maarten Flippo – Mentor (TU Delft - Algorithmics)
E. Demirović – Mentor (TU Delft - Algorithmics)
Benedikt Ahrens – Graduation committee member (TU Delft - Programming Languages)
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
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.