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].

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.

  • 5
    $\begingroup$ Apparently the claims of NP-completeness of pallet loading are erroneous, according to this: cs.smith.edu/~orourke/TOPP/P55.html Do you have a more recent reference? $\endgroup$ – Alessandro Cosentino Jan 11 '13 at 16:51
  • 3
    $\begingroup$ @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 ..." $\endgroup$ – Marzio De Biasi Jan 11 '13 at 17:09
  • 4
    $\begingroup$ 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 en.wikipedia.org/wiki/Square_packing_in_a_square. $\endgroup$ – SamM Jan 11 '13 at 17:43
  • 3
    $\begingroup$ @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" ) $\endgroup$ – Marzio De Biasi Jan 11 '13 at 23:25
  • 2
    $\begingroup$ @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. $\endgroup$ – usul Jan 12 '13 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.