Excuse the non-mathematical way I've phrased the question.

I have the following problem:

  1. I have $N$ square paper documents with side lengths between $150$mm and $860$mm. I know each document side's length.

  2. I need to create $3-4$ differently sized boxes to fit all the documents, e.g. Three box types: Box $1$ side $l_1=300$mm, Box $2$ side $l_2=600$mm, Box $3$: $l_3=860$mm.

  3. There are as many boxes as documents, i.e. each document goes into its own separate box (of the smallest possible size so as to minimize waste of cardboard).

  4. What is the best way to decide on the size of the boxes, so as to minimize the total amount of (surface area) of cardboard used?

I'm not necessarily looking for the analytical solution to this problem. Two ideas I've had:

a) Pick $l_1$ and $l_2$ values at random and calculate the total surface area of cardboard. Guess the values again, see if the total surface area is smaller, and so on and on.

b) A more analytical approach where I'm computing $l_1$ and $l_2$ value in say $1$mm increments and I calculate the total surface area for each combination of box lengths between say ($150$mm, $151$nmm,$860$mm) and ($858$mm,$859$mm,$860$mm).

What would you suggest is the most practical way of going about solving this?

BTW, I'm great with Excel, less so with Mathlab, etc. I can program well in Ruby if that helps in any way.

  • Do all the boxes have the same height? Since you have to have one box of the largest size in any event, why doesn't having one box of this size minimize the amount of cardboard? There must be information you're not telling us. – saulspatz Jul 7 at 23:57
  • Yes, we can assume all boxes have the same height. I'm not entirely sure I've understood your second question...I'm assuming there will need to be at least one box of the largest size, i.e. 860mm length so that the largest square document can fit inside it. – pizu Jul 8 at 9:59
  • Why can't we simply put all the documents in the largest box? – saulspatz Jul 8 at 13:10
  • We're trying to minimize the waste. If a document can be put in a small or medium sized box rather than the biggest one, then that's a lot less waste. – pizu Jul 9 at 16:18
  • FYI If someone is having a similar challenge. I found a couple of solutions... 1. My favourite one is such that I pick three box sizes value at random e.g. (160, 350, 860) then I compute the total area of cardboard used for the entire set of 1200 documents. I repeat the above step and note down the total area if it's smaller than for the previous guess. I find that 0.5-1 million of guesses get me to the right answer. The ruby code is actually quite simple. – pizu Jul 9 at 16:19

As Erwin points out in his blog post, you can model this as a network. I would take that approach, in part because it requires no specialized software. Per Erwin's post, you have 384 distinct paper sizes. Create one node for each, and let $s_i$ be the paper size for node $i$ and $n_i$ the count for size $i$. For each pair of nodes $i < j$, draw an arc from node $i$ to node $j$ whose cost is $s_j^2 \sum_{k=i+1}^j n_k$. This arc represents the cost (surface area) of putting all pages with sizes between $s_{i+1}$ and $s_j$ into boxes of size $s_j$.

You can now iterate over the graph using either two or three nested loops (since you limited yourself to three or four box sizes). Start at node 1 and look at each possible successor node (outer loop), each possible successor to that node (inner loop), each possible successor to that node (nested loop if you are allowing four sizes), recognizing that you must take the arc from the node in the innermost loop to node 384. You sum the lengths of the selected arcs, then compare the sum to the best solution so far. If it's shorter, update the best solution. Finally, note that you can break off any inner loop if its cumulative sum equals or exceeds the best some so far, since adding more (positive) arc costs cannot reduce the sum.

I would not advocate brute force in general, but with a maximum of four box sizes, and given the speed of a contemporary PC, this should be rather doable (and, again, requires no special software, other than a compiler/interpreter for some programming language).

  • I'm going to amend this, because I think it can be more efficient. Assume a limit of four box sizes. Create a layered network with six layers. The first and last layers contain just start and end nodes. The second layer has 384 nodes, one for each size. The third layer has 383 nodes (omits the smallest size), the fourth has 382 nodes (omits the two smallest sizes), and the fifth has 381 nodes. Arcs and arc weights are as above, with arcs from any node to all nodes in the next layer that are bigger sizes. The shortest path from start to end is the winner. For three box sizes, drop one layer. – prubin Jul 17 at 14:51
  • Sorry -- even what I wrote in the comment is a little overblown. You know you have to use the largest box size (to hold the largest documents), so that sixth layer and the end node are redundant. The fifth layer will contain just one node, for the largest document size, and that will be the terminus. Also, layer four will omit the largest size (coming in layer five), layer three will omit the two largest sizes, etc. – prubin Jul 17 at 17:45
  • Last comment to myself (I hope): I coded this in Java and ran it. My results confirm Erwin's answers as far as total size of boxes used. On a decent PC (Intel quad core processor, 12 GB of RAM), the case of 3 box sizes took 318 ms. (including reading the data in), while 4 box sizes took 518 ms. This is without using parallel threads. – prubin Jul 17 at 18:59

I have modeled this as a set covering problem, similar as in link.

The first step was to condense the data, by only storing the unique values and their count. This reduces the data from 1166 to 384 records. Make sure they are ordered by increasing size.

Then I define a binary variable

$$x_{i,j} = \begin{cases}1 & \text{if we put items $i$ through $j$ in the same box sizes $j$}\\ 0 & \text{otherwise}\end{cases}$$

Every item $k$ must be covered exactly once by a variable $x_{i,j}$. This leads to:

$$\sum_{i \le k \le j} x_{i,j} = 1 \>\>\text{ for all items $k$}$$

We need to cover exactly once, so this is sometimes called a set partitioning problem.

We have 4 different box sizes, so:

$$\sum_{i \le j} x_{i,j} = 4$$

The objective is

$$\min \sum_{i \le j} c_{i,j} x_{i,j}$$

where $c_{i,j}$ is the total area, i.e.

$$ c_{i,j} = \sum_{i \le k \le j} \mathit{count}_k \mathit{area}_j $$

This leads to a very large but easy MIP (Mixed Integer Programming) model. Its size is:

MODEL STATISTICS

BLOCKS OF EQUATIONS           3     SINGLE EQUATIONS          386
BLOCKS OF VARIABLES           2     SINGLE VARIABLES       73,921
NON ZERO ELEMENTS     9,658,881     DISCRETE VARIABLES     73,920

It takes about a minute to solve (on a slow laptop). The results look like:

----    443 PARAMETER results  

                 count     minsize     maxsize        area    sum area

i1   .i155     549.000     156.000     388.000  150544.000 8.264866E+7
i156 .i268     377.000     389.000     550.000  302500.000 1.140425E+8
i269 .i351     187.000     552.000     705.000  497025.000 9.294368E+7
i352 .i384      53.000     710.000     864.000  746496.000 3.956429E+7
total.        1166.000                                     3.291991E+8

This is a proven optimal solution.

For 3 different boxes I get:

----    443 PARAMETER results  

                 count     minsize     maxsize        area    sum area

i1   .i155     549.000     156.000     388.000  150544.000 8.264866E+7
i156 .i284     423.000     389.000     574.000  329476.000 1.393683E+8
i285 .i384     194.000     576.000     864.000  746496.000 1.448202E+8
total.        1166.000                                     3.668372E+8

As expected the objective deteriorates: we waste more space. Interestingly the smallest boxes are the same as for the previous case.

Alternative methods includes a network approach (see the answer by Paul Rubin) or a Dynamic Programming algorithm. Somehow I like the set partitioning model: the constraints can be written very compactly (and actually make intuitive sense).

A Dynamic Programming algorithm in R can look like:

data <- c(
 156,162,168,178,178,180,185,185,190,192,193,194,195,195,
 . . .
 805,806,820,823,827,827,855,855,864)

# get unique values and counts
t<-table(data)
count <- as.vector(t)
size <- as.numeric(rownames(t))

cumulative <- cumsum(count)

# number of box sizes, number of item sizes
NB <- 4
NI <- length(size)

# allocate matrix NI rows, NB columns (initialize with NAs)
# f[ni,nb] = cost when we have ni items and nb blocks
F <- matrix(NA,NI,NB)
S <- matrix("",NI,NB)

# initialize for nb=1
F[1:NI,1] <- cumulative * size[1:NI]^2
S[1:NI,1] <- paste("(",1,"-",1:NI,")",sep="")

# dyn programming loop
for (nb in 2:NB) {
  for (ni in nb:NI) {
     k <- (nb-1):(ni-1)
     v <- F[k,nb-1] + (cumulative[ni]-cumulative[k])*size[ni]^2
     F[ni,nb] <- min(v)

     # create path (string)
     mink <- which.min(v) + nb - 2
     s <- paste("(",mink+1,"-",ni,")",sep="")
     S[ni,nb] <- paste(S[mink,nb-1],s,sep=",")
  }
}

for (nb in 1:NB) {
   cat(sprintf("%s boxes: %s, total area = %g\n",nb,S[NI,nb],F[NI,nb]))
}

The solution looks like:

1 boxes: (1-384), total area = 8.70414e+08
2 boxes: (1-268),(269-384), total area = 4.59274e+08
3 boxes: (1-155),(156-284),(285-384), total area = 3.66837e+08
4 boxes: (1-155),(156-268),(269-351),(352-384), total area = 3.29199e+08

We found the same solution as with the other methods.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.