Algorithm for combining numbers into optimal groups which do not exceed a vector of max values?

Question

I'm cutting trim molding for my house and have various lengths of trim pieces, and would like to group them optimally for the smallest amount of waste. Basically, I'm trying to optimally group (or pack) the required lengths into the available longer lengths.

I'm a bit stumped on how to approach this and have currently just been doing it by hand, however a mistake ends up causing me to re-work the whole operation. I know some java, but have recently been working exlusively with R, so that's my most familiar language at this point. Are there suggestions for how to approach this?

Is there a better way of doing this than manually looping through with an algorithm something like this (I'm just sketching the idea; don't look for correct syntax):

trim_lengths <- c(44, 57, 86, 86, 40, 88, 88, 41, 40, 40,
  62, 62, 54, 54, 55, 55, 63, 63, 75, 75, 100, 100)

avail_lengths <- c(120, 103, rep(100, 9), 98, rep(97, 4),
  95, rep(88, 3), 85, 65)

while(length(trim_lengths) > 0) {
  current_max <- max(trim_lengths)
  current_min <- min(trim_lengths)

  if(current_max + current_min > max(avail_lengths) {
    find smallest value in avail_lengths that's greater than current_max
    store current_max and optimal value from avail_lengths in list or vector
      to indicate the pairing/grouping
  }

  else {
    group <- c(current_max, current_min)
    current_max <- trim_lengths minux elements in group
    if <- sum(group) + current_max > max(avail_lengths) {
      store group and corresponding avail_length element in list/vector
    }

    else{
      basically, keep trying to group until solved
    }
  }

I already know that's not optimal, as it's checking from the "outside in" on the trim_lengths vector, and my hand-done pairings often end up pairing a small and mid level value into an available length that's pretty easy to see is just an inch or two longer than said pairing.

Anyway, it was an interesting problem and I wondered if there were references or obvious suggestions that would come to mind for a solution. In some of the related questions the first comment often asked, "What did you try." I really haven't... as I'm stumped at the moment. The only other thing I thought of was brute-forcing combinations randomly, storing the solution that minimizes waste.

I'd love some suggestions on solving this in a vectorized way -- some sort of matrix operation, or perhaps a linear model representation of the problem. I'll keep thinking on it as well.

Answer 1

 courtesy of http://xkcd.com/287/

(yes, this is a comment, not an answer. If only imgs could load in the little tiny comment line)

Answer 2

This multiple-knapsack problem seemed like a fun one to try using lpSolveAPI, which is what I did. I used an Integer Programming approach to find the optimal solution to your trim problem.

First, here's what the solution I found looks like:

As you can see, there were 5 available pieces that weren't needed at all. (100% surplus)

Formulation

• Let a_1, a_2, ..., a_k be the available piece lengths.

• Let t_1, t_2, ..., t_n be the required trim lengths.

• Variables: Let X_a_t be 1 if trim t is cut from available piece a, 0 otherwise

Define Surplus_i to be A_i minus the sum over j=1..n of (X_a_t * t_j)

• Objective: Minimize Sum of Surplus_i for all A's (1..k)

Constraints

• Set Partitioning Constraint: (in English) Every trim must be cut from some piece

    Sum over A(1..k) X_a_t = 1 for all t (1..n)
  

Also, all surpluses have to be >= 0 # no negatives allowed

A_i - sum over j in 1..k X_ai_tj * t_j  = Surplus_i (for each Ai) # definitional constraint.

R Code using lpSolveAPI

In my A-matrix (the first set of columns are Surplusses variables, and the next set are X_a_t variables. The first set of constraints are "set cover" constraints. The second set of constraints are "surplus" non-negativity constraints. Examine the trimIP.lp file to view the full formulation.

Warning: The code is longer than I'd have liked, but here it is:

library(lpSolveAPI)

#Problem definition
trim.lengths <- c(44, 57, 86, 86, 40, 88, 88, 41, 40, 40, 62, 62, 54, 54, 55, 55, 63, 63, 75, 75, 100, 100)
avail.lengths <- c(120, 103, rep(100, 9), 98, rep(97, 4), 95, rep(88, 3), 85, 65)
num.trims = length(trim_lengths) #22
num.avail = length(avail.lengths) #22
a.set<-1:num.avail
t.set <- 1:num.trims

#set rownames & colnames
setRowAndColNames<- function() {  
  a.and.t<- t(outer(a.set, t.set, paste, sep="_"))
  col.names <- paste("x_", a.and.t, sep="")
  s.vars <- paste("Surplus_", a.set, sep="")
  c.names <- c(s.vars, col.names)
  r.names <- setRowNames() 
  return( list(r.names, c.names)  )
}

setRowNames <- function() {
  cover.rows<- paste("CoverTrim", t.set, sep="_") #Cover constraints
  surplus.rows <- paste("DefineSurplus", a.set, sep="_") #non-neg constraints
  r.names <- c(cover.rows, surplus.rows)
  return(r.names)
}

populate.Amatrix <- function() {  
  df <- data.frame(matrix(0, n.rows, n.cols))  #create a dataframe shell  
  for (row in 1:num.trims) {
    skip = num.avail #for the surplus variables
    cols <- seq(0, (num.trims*num.avail)-1, by=num.avail)    
    df[row, skip+cols+row] <- 1
  }
  print("Done with cover Trims Constraints")
  st.row <- num.trims+1
  end.row<- st.row+num.avail-1
  for (row in st.row:end.row) {
    surplus.column <- row - num.trims
    df[row,surplus.column] <- 1
    current.a <- surplus.column
    acols <- num.avail + ((current.a-1)*num.trims) + (1:num.trims)
    df[row,acols] <- trim.lengths

  }
  return(df)
}


defineIP <- function(lp) {
  obj.vector <- c(rep(1, num.avail), rep(0, num.avail*num.trims))
  set.objfn(lp, obj.vector ) #minimize surplusses
  set.constr.type(lp, rep("=", n.rows), 1:n.rows) 
  rhs.vector <- c(rep(1, num.avail), avail.lengths)
  set.rhs(lp, b=rhs.vector, constraints=1:n.rows) # assign rhs values   

  #Set all the columns at once
  for (col in 1:n.cols) {
    set.column(lp, col, df[ ,col])  
  }

  for (col in (num.avail+1):n.cols) {
    print(col)
    set.type(lp, col, "binary")      
  }

  #assemble it all
  dimnames(lp) <- setRowAndColNames()
  write.lp(lp, "trimIP.lp", "lp")#write it out
}


# actual problem definition
n.rows <- num.trims + num.avail
n.cols <- (num.avail+1) * num.trims  #the extra one is for surplus variables
df <- populate.Amatrix()

lptrim <- make.lp(nrow=n.rows, ncol=n.cols)
defineIP(lptrim)
lptrim
solve(lptrim)
sol <- get.variables(lptrim)
sol <- c(sol, trim.lengths)
sol.df <- data.frame(matrix(sol, nrow=24, ncol=22 , byrow=T)) #you can examine the solution data frame

If you want to reproduce the entire exercise, I placed the code as a github gist