Analysis of upper bounds for the pallet loading problem

Analysis of upper bounds for the pallet loading problem

0.00 Avg rating0 Votes
Article ID: iaor20021733
Country: Netherlands
Volume: 132
Issue: 3
Start Page Number: 582
End Page Number: 593
Publication Date: Aug 2001
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: mathematical
Abstract:

This paper is concerned with upper bounds for the well-known Pallet Loading Problem, which is the problem of packing identical boxes into a rectangular pallet so as to maximize the number of boxes fitted. After giving a comprehensive review of the known upper bounds in the literature, we conduct a detailed analysis to determine which bounds dominate which others. The result is a ranking of the bounds in a partial order. It turns out that two of the bounds dominate all others: a bound due to Nelissen and a bound obtained from the linear programming relaxation of a set packing formulation. Experiments show that the latter is almost always optimal and can be computed quickly.

Reviews

Required fields are marked *. Your email address will not be published.