The Open Problems Project

Next: Problem 56: Packing Unit Squares in a Simple Polygon

Previous: Problem 54: Traveling Salesman Problem in Solid Grid Graphs

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 \times b, in either axis-parallel orientation, can be packed into a large rectangle of size A \times 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.