Next: Problem 56: Packing Unit Squares in a Simple Polygon
Previous: Problem 54: Traveling Salesman Problem in Solid Grid Graphs
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.
Uncertain, pending investigation.
Open.
Natural packing problem; first-rate example of the relevance of coding input and output.
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.
What is the complexity of packing a maximal number of unit squares in a simple polygon? (Problem 54)
[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].
packing; optimization
S. P. Fekete, 17 Jan. 2004.
K. A. Dowsland. An exact algorithm for the pallet loading problem. European Journal of Operational Research, 31:78–84, 1987.
H. Exeler. Das homogene Packproblem in der betriebswirtschaftlichen Praxis. Physica-Verlag, Heidelberg, 1988.
J. Nelißen. New approaches to the pallet loading problem. Technical report, RWTH Aachen, 1993.
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.