Need to create $3-4$ different box sizes and to minimize material waste for a set of $n$ objects that need to fit into these boxes

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.