next up previous
Next: Problem 56: Packing Unit Up: The Open Problems Project Previous: Problem 54: Traveling Salesman


Problem 55: Pallet Loading

Statement
What is the complexity of the pallet loading problem? Given two pairs of numbers, (A, B) and (a, b), and a number n, decide whether n small rectangles of size a×b, in either axis-parallel orientation, can be packed into a large rectangle of size A×B.

This problem is not even known to be in NP, because of the compact input description, and the possibly complicated structure of a packing, if there is one.

Origin
Uncertain, pending investigation.
Status/Conjectures
Open.
Motivation
Natural packing problem; first-rate example of the relevance of coding input and output.
Partial and Related Results
Tarnowsky [Tar92] showed that the problem can be solved in time polynomial in the size of the input if we are restricted to ``guillotine'' patterns, i.e., arrangements of items that can be obtained by a recursive sequence of edge-to-edge cuts. This result uses some nontrivial algebraic methods.
Related Open Problems
What is the complexity of packing a maximal number of unit squares in a simple polygon? (Problem 54)
Appearances
[Dow87] claims the problem to be NP-hard; [Exe88] claims the problem to be in NP; but both claims are erroneous. The precise nature of the difficulty is stated in [Nel93].
Categories
packing; optimization
Entry Revision History
S. P. Fekete, 17 Jan. 2004.

Bibliography

Dow87
K. A. Dowsland.
An exact algorithm for the pallet loading problem.
European Journal of Operational Research, 31:78-84, 1987.

Exe88
H. Exeler.
Das homogene Packproblem in der betriebswirtschaftlichen Praxis.
Physica-Verlag, Heidelberg, 1988.

Nel93
J. Nelißen.
New approaches to the pallet loading problem.
Technical report, RWTH Aachen, 1993.

Tar92
A. G. Tarnowsky.
Exact polynomial algorithm for special case of the two-dimensional cutting stock problem: A guillotine pallet loading problem.
Technical Report 9205 - DO, Belarusian State University, 1992.


next up previous
Next: Problem 56: Packing Unit Up: The Open Problems Project Previous: Problem 54: Traveling Salesman
The Open Problems Project - December 08, 2012