You are here

Failure detection for the Bin-Packing Constraint

TitleFailure detection for the Bin-Packing Constraint
Publication TypeConference Paper
Year of Publication2009
AuthorsDupuis, Julien, Schaus Pierre, and Deville Yves
Conference NameSecond International Workshop on Bin Packing and Placement Constraints (BPPC'09)
Date Published20/09/2009
Keywordsbin-packing, failure detection, pack constraint, reduction

In addition to a filtering algorithm, the Pack constraint introduced by Shaw 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 (BPLB) on the reduced problem. A first possible improvement on Shaw?s test is to use a stronger BPLB. In particular, Labbé ?s lower bound was recently proved to dominate Martello?s lower bound used by Shaw. A second possible improvement is to use a reduction different from the one introduced by Shaw. We propose two new reduction algorithms and prove that one of them theoretically dominates the others. All the proposed improvements on the failure test are evaluated using the COMET System.