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 fo r the pallet loading problem of packing identical rectangles, orthogon ally, 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 meth od based on a set of structural constraints for a solution which reali zes the assumed upper bound. The constraints spring from a linear prog ramming problem which is solved for various cost functions. By means o f several arguments, these constraints can be gradually tightened. If this leads to a contradiction, then the upper bound estimate was too h igh and must be decremented. This method is shown to be accurate for a ll but 28 problems in a random sample of 20000 - an improvement of 262 over previous methods.