You are here

Consistency check for the bin packing constraint revisited

TitleConsistency check for the bin packing constraint revisited
Publication TypeConference Paper
Year of Publication2010
AuthorsDupuis, Julien, Schaus Pierre, and Deville Yves
Conference NameCPAIOR 2010
Date Published14/06/2010
PublisherSpringer Berlin / Heidelberg
Conference LocationBologna
ISBN Number978-3-642-13519-4
Keywordsbin packing, constraint programming, reduction

In addition to a filtering algorithm, the Pack constraint for bin packing introduced by Shaw [Shaw04] uses a failure detection algorithm. This test is based on a reduction of the partial solution to a standard bin packing problem and the computation of a bin packing lower bound on the reduced problem. We propose two new reduction algorithms and prove that one of them theoretically dominates the others. Experimental results show that a combination of our reductions improves the quality of the failure detection.