Complexity of the pallet loading problem
In the pallet loading problem the input is two pairs of numbers $(A,B)$ and $(a,b)$ and a number $n$, and one must decide whether $n$ rectangles of size $a \times b$, each placed axis-parallel in either of its two orientations, can be packed into a rectangle of size $A \times B$. Not even membership in NP has been established: the input is very compact, and a packing, if one exists, may have a complicated structure.
Tarnowsky showed, using nontrivial algebraic methods, that the problem is solvable in time polynomial in the input size when only guillotine packings are allowed, those that can be cut out by repeatedly splitting a rectangle with a straight cut from one side to the opposite side. Dowsland claimed the problem NP-hard and Exeler claimed it lies in NP; both claims are mistaken, and Nelißen explains where the difficulty lies.
Problem. What is the computational complexity of the pallet loading problem?
Source: Origin uncertain; Problem 55 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- OC — Optimization and Control
- Secondary
- CO, MG
- Keywords
- computational complexity, pallet loading, rectangle packing, The Open Problems Project
References
@techreport{tarnowsky1992,
author = {Tarnowsky, A. G.},
title = {Exact polynomial algorithm for special case of the two-dimensional cutting stock problem: A guillotine pallet loading problem},
institution = {Belarusian State University},
number = {9205-DO},
year = {1992},
}
@article{dowsland1987,
author = {Dowsland, K. A.},
title = {An exact algorithm for the pallet loading problem},
journal = {European J. Oper. Res.},
volume = {31},
year = {1987},
pages = {78--84},
}
@book{exeler1988,
author = {Exeler, H.},
title = {Das homogene {P}ackproblem in der betriebswirtschaftlichen {P}raxis},
publisher = {Physica-Verlag},
address = {Heidelberg},
year = {1988},
}
@techreport{nelissen1993,
author = {Neli{\ss}en, J.},
title = {New approaches to the pallet loading problem},
institution = {RWTH Aachen},
year = {1993},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01095, "Complexity of the pallet loading problem", clopen.solutions.