5
$\begingroup$

Real world problem alert: I am moving from my house to another one, and the problem below arised when I tried to fit some little boxes of various shapes into a large box:

We are given a positive integer $n$ and $3$-tuples consisting of positive rationals $(w_i, l_i, h_i)$ for $i \in \{1,\ldots,n\}$. For each $i$, the tuple $(w_i, l_i, h_i)$ represents a box of width $w_i$, length $l_i$, and height $h_i$.

We want to put these $n$ boxes into one big box of rational dimensions $(W, L, H)$ such that the volume $W\cdot L\cdot H$ of the big box is minimal.

Is the problem of finding (one possible choice of) $(W,L,H)$, such that $WLH$ is minimized, computable?

EDIT. Thanks to Reid Barton and Tony Huynh for their comments below. The boxes can be rotated arbitrarily.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Are we allowed to rotate the boxes arbitrarily? $\endgroup$
    – Reid Barton
    Commented Apr 26, 2019 at 13:01
  • $\begingroup$ That's a good question! I am inclined to say "yes", but then I am not sure minimal values for $W, L, H$ necessarily exist? (There are surely infimum values.) - But let's make the problem more interested, and allow for arbitrary rotation of the boxes $\endgroup$
    – Dominic van der Zypen
    Commented Apr 26, 2019 at 18:27
  • 5
    $\begingroup$ If you are not allowed to rotate the boxes arbitrarily, the answer is clearly yes. Just scale so that all distances are integer. Then the solution lives on the $M \times M \times M$ integer lattice where $M$ is the maximum of the sum of the widths, lengths and heights. So you can just try all possibilities. $\endgroup$
    – Tony Huynh
    Commented Apr 27, 2019 at 9:12

2 Answers 2

Reset to default
4
$\begingroup$

This is not an answer, but instead addresses a related problem: The problem of finding a minimum area rectangle that encloses a given set of rectangles, without rotation (i.e., all sides parallel to Cartesian $x$ & $y$ axes) is NP-hard.

Huang, Eric, and Richard E. Korf. "Optimal packing of high-precision rectangles." In Twenty-Fifth AAAI Conference on Artificial Intelligence. 2011. PDF download.

Korf, Richard E. "Optimal Rectangle Packing: Initial Results." In ICAPS, pp. 287-295. 2003. PDF download.

          Squares22
          Korf (2003): Optimal packing of the first 22 squares.

Improve this answer
$\endgroup$
4
$\begingroup$

Yes, this is computable. And the infimum is attained. To see this, observe you can express a placement of your boxes by giving the coordinates of each box corner together with the angles. Then this placement is a valid packing if a (big) collection of simple inequalities are satisfied. It's clear that there are only finitely many combinatorially different placements (as defined, say, by extending all the bounding planes and looking at the combinatorial structure of the corresponding arrangement of planes) and hence one can simply minimise (continuously, hence attaining the minimum) over each structure. This is (a) possible, actually fairly easily, but Tarski's theorem is easier to quote, and (b) not in any way an efficient algorithm..!

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .