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: | Letchford Adam N., Amaral Andr R.S. |
Keywords: | programming: mathematical |
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.