<p>In the pallet loading problem, we are asked to place a set of small identical 2-D rigid objects into a large bounding rectangle such that no two objects overlap.  This problem is a special case of the cutting stock problem and is known to be NP-complete.  It is NP-complete even for the special case in which the objects are identical squares<a href="http://www.sciencedirect.com/science/article/pii/0020019081901113"> [Fowler, Paterson, Tanimoto 1981]</a>.</p>

<p>Is pallet loading also NP-complete when the objects are non-rectangular? In particular, I am interested the case in which the objects are octagons.</p>

CC BY-SA 3.0
2013-01-11T16:51:12.370Z
Apparently the claims of NP-completeness of pallet loading are erroneous, according to this: http://cs.smith.edu/~orourke/TOPP/P55.html Do you have a more recent reference?
Alessandro Cosentino
CC BY-SA 3.0
2013-01-11T17:09:12.920Z
@AlessandroCosentino: the entry revision of Problem 55 is rather old (2004); but in a more recent paper by Birgin, Lobato, and Morabito "An effective recursive partitioning approach for the packing of identical rectangles in a rectangle" (2007) I found: "... Apparently easy to be optimally solved, the problem is claimed to be NP-hard although it has not been proven ..."
Marzio De Biasi
CC BY-SA 3.0
2013-01-11T17:11:06.317Z
If identical squares must be packed in a rectangular pallet the problem should be (trivially) in P ?!?
Marzio De Biasi
CC BY-SA 3.0
2013-01-11T17:43:59.857Z
I think it's far from trivial as packing squares into a square is fairly non-obvious; in fact it's open for many numbers of squares http://en.wikipedia.org/wiki/Square_packing_in_a_square.
SamM
CC BY-SA 3.0
2013-01-11T19:24:42.607Z
Can you define the decision problem more precisely? As I understand it, the cutting stock problem is akin to being given the set of squares and asked to find the smallest "pallet" in which they fit. The pallet loading problem is, given a certain-size pallet and the size/shape of the object, what is the maximum number of copies of the object that fit inside?
usul
CC BY-SA 3.0
2013-01-11T23:25:04.603Z
@SamM: you're right (I was thinking only of orthogonal packing)! It's far from being trivial ... (see also "[Packing Unit Squares in Squares: A Survey and New Results](http://www1.combinatorics.org/Surveys/ds7.html)" )
Marzio De Biasi
CC BY-SA 3.0
2013-01-12T16:18:24.353Z
@usul: The decision problem is stated as follows. Given a rectangle of dimension $x \times y$ and some number of objects $k$, is there a way to place all $k$ objects inside of the rectangle such that none of them overlap?
Adam Paetznick
CC BY-SA 3.0
2013-01-12T16:49:02.557Z
@Adam: So to be sure I understand, the inputs are the numbers $x$, $y$, and $k$, and a polygon describing the size and shape of the small object.
usul
CC BY-SA 3.0
2013-01-12T22:57:37.667Z
@usul: that is correct
Adam Paetznick
<np-hardness><packing>
What is the complexity of pallet loading for identical non-rectangular objects?
Adam Paetznick
# What is the complexity of pallet loading for identical non-rectangular objects?

(Asked by: username_0 on 2013-01-11)

In the pallet loading problem, we are asked to place a set of small identical 2-D rigid objects into a large bounding rectangle such that no two objects overlap. This problem is a special case of the cutting stock problem and is known to be NP-complete. It is NP-complete even for the special case in which the objects are identical squares [[Fowler, Paterson, Tanimoto 1981]](http://www.sciencedirect.com/science/article/pii/0020019081901113).

Is pallet loading also NP-complete when the objects are non-rectangular? In particular, I am interested the case in which the objects are octagons.

**Tags:** np-hardness, packing
> **Comments:**
> **username_1**: Apparently the claims of NP-completeness of pallet loading are erroneous, according to this: http://cs.smith.edu/~orourke/TOPP/P55.html Do you have a more recent reference?  
> **username_2**: @AlessandroCosentino: the entry revision of Problem 55 is rather old (2004); but in a more recent paper by Birgin, Lobato, and Morabito "An effective recursive partitioning approach for the packing of identical rectangles in a rectangle" (2007) I found: "... Apparently easy to be optimally solved, the problem is claimed to be NP-hard although it has not been proven ..."  
> **username_2**: If identical squares must be packed in a rectangular pallet the problem should be (trivially) in P ?!?  
> **username_3**: I think it's far from trivial as packing squares into a square is fairly non-obvious; in fact it's open for many numbers of squares http://en.wikipedia.org/wiki/Square_packing_in_a_square.  
> **username_4**: Can you define the decision problem more precisely? As I understand it, the cutting stock problem is akin to being given the set of squares and asked to find the smallest "pallet" in which they fit. The pallet loading problem is, given a certain-size pallet and the size/shape of the object, what is the maximum number of copies of the object that fit inside?  
> **username_2**: @SamM: you're right (I was thinking only of orthogonal packing)! It's far from being trivial ... (see also "[Packing Unit Squares in Squares: A Survey and New Results](http://www1.combinatorics.org/Surveys/ds7.html)" )  
> **username_0**: @usul: The decision problem is stated as follows. Given a rectangle of dimension $x \times y$ and some number of objects $k$, is there a way to place all $k$ objects inside of the rectangle such that none of them overlap?  
> **username_4**: @Adam: So to be sure I understand, the inputs are the numbers $x$, $y$, and $k$, and a polygon describing the size and shape of the small object.  
> **username_0**: @usul: that is correct  

---

## 0 answers

