How to use structural constraints to compute an upper bound for the pallet loading problem

During the last twenty years several heuristics have been developed for the pallet loading problem of packing identical rectangles, orthogonally, into a large containing rectangle. Upper bound methods are used to verify the optimality of heuristic solutions. If these methods fail, exact algorithms have to be applied, which may require a prohibitive amount of computing time. This paper discusses a new upper bound method based on a set of structural constraints for a solution which realizes the assumed upper bound. The constraints spring from a linear programming problem which is solved for various cost functions. By means of several arguments, these constraints can be gradually tightened. If this leads to a contradiction, then the upper bound estimate was too high and must be decremented. This method is shown to be accurate for all but 28 problems in a random sample of 20 000 – an improvement of 262 over previous methods.