Improved filtering for the bin-packing with cardinality constraint
(2017) Constraints : an international journal — Vol. 23, p. 251-271 (2018)
Files
ImprovedBPC.pdf
Open Access - Adobe PDF
- 375.34 KB
Details
- Authors
Derval, Guillaume 
- Abstract
- Previous research shows that a cardinality reasoning can improve the pruning of the bin-packing constraint. We first introduce a new algorithm, called BPCFlow, that filters both load and cardinality bounds on the bins, using a flow reasoning similar to the Global Cardinality Constraint. Moreover, we detect impossible assignments of items by combining the load and cardinality of the bins, using a method to detect items that are either ”too-big” or ”too-small”. This method is adapted to two previously existing filtering techniques along with BPCFlow, creating three new propagators. We then experiment the four new algorithms on Balanced Academic Curriculum Problem and Tank Allocation Problem instances. BPCFlow is shown to be stronger than previously existing filtering, and more computationally intensive. We show that the new filtering is useful on a small number of hard instances, while being too expensive for general use. Our results show that the introduced ”too-big/too-small” filtering can most of the time drastically reduce the size of the search tree and the computation time. This method is profitable in 88% of the tested instances.
- Affiliations
Citations
Derval, G., Régin, J.-C., & Schaus, P. (2017). Improved filtering for the bin-packing with cardinality constraint. Constraints : an international journal, 23, 251-271. https://doi.org/10.1007/s10601-017-9278-x (Original work published 2018)