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.