Алгоритм объединения чисел в оптимальные группы, не превышающие вектор максимальных значений?

Question

Я занимаюсь резкой отделкой для моего дома и имеет различные длины отделочных деталей и хотел бы оптимально сгруппировать их для наименьшего количества отходов. В принципе, я пытаюсь оптимально группировать (или упаковывать) требуемые длины в доступные более длинные длины.

Я немного зациклен на том, как подойти к этому и в настоящее время только что делал это вручную, однако ошибка заканчивается тем, что заставляет меня перерабатывать всю операцию. Я знаю некоторые java, но недавно работал исключительно с R, так что это мой самый знакомый язык на данный момент. Есть ли предложения о том, как подойти к этому?

Есть ли лучший способ сделать это, чем зацикливание вручную с помощью алгоритма что-то вроде этого (я просто набрасывать идею, не ищет правильный синтаксис):

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 
    } 
    } 

Я уже знаю это не оптимально, так как он проверяет «вне дома» на векторе trim_lengths, и мои ручные пары часто заканчиваются тем, что сопрягают небольшое и среднее значение уровня с доступной длиной, которую довольно легко увидеть, всего на дюйм или два дольше чем указанное спаривание.

В любом случае, это была интересная проблема, и я подумал, есть ли ссылки или очевидные предложения, которые придут на ум для решения. В некоторых из связанных вопросов первый комментарий часто спрашивал: «Что вы пробовали». У меня действительно нет ... как я в тупик. Единственное, что я думал о том, что это были беспорядочные комбинации, случайным образом, хранение решения, которое сводит к минимуму трату.

Мне понравились бы некоторые предложения по решению этого в векторном виде - некоторая операция с матрицей или, возможно, линейное представление модели проблемы. Я тоже буду думать об этом.

Answer 1

любезноhttp://xkcd.com/287/

(да, это комментарий, а не ответ. Если только ГИМ может загрузить в крохотных строке комментария)

Answer 2

кажется мне больше как 1 -D резка проблема. Посмотрите на http://en.wikipedia.org/wiki/Cutting_stock_problem Существует довольно немного на эту тему.

Надеюсь, это поможет. Мне просто нравится, когда у кого-то есть практическая проблема, когда они делают что-то реальное и на самом деле думают о том, как решить свою проблему, а не просто слепо обвинять. Очень мощные возможности для обучения ... просто не так зацикливайтесь на технических замысловатости, которые вы забываете на самом деле тоже делать!

Answer 3

Рассматривали ли вы использование генетического алгоритма?

Answer 4

Эта проблема multiple-knapsack показалась забавной, чтобы попытаться использовать lpSolveAPI, что и я сделал. Я использовал метод Integer Programming для поиска оптимального решения вашей проблемы с обрезкой.

Во-первых, вот что решение, которое я нашел, как выглядит:

Как вы можете видеть, там было 5 доступных частей, которые не нужны вообще.(100% избыток)

Формулирование

• Пусть a_1, a_2, ..., a_k быть доступны длины шт.

• Пусть t_1, t_2, ..., t_n - требуемая длина отделки.

• Переменные: Пусть X_a_t 1, если обрезать т вырезан из доступного куска , 0 в противном случае

Определение Surplus_i быть A_i минус сумма по J = 1..N из (X_a_t * T_j)

• Цель: Минимизация суммы Surplus_i для всех А в (1..k)

Ограничения

• Set Разметка Constraint: (на английском языке) Каждая отделка должна быть вырезана из какой-то части

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

Кроме того, все излишки должны быть> = 0 # не допускается никаких отрицательных последствий

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

R-код с использованием lpSolveAPI

В моей A-матрице (первый набор столбцов - переменные Surplusses, а следующий набор - переменные X_a_t. Первый набор ограничений - это ограничения «установить обложку». Второй набор ограничений - это «избыточные» ограничения негатива. Изучите файл trimIP.lp, чтобы просмотреть полную формулировку.

Внимание: код больше, чем я бы хотел, но вот это:

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 

Если вы хотите, чтобы воспроизвести всю работу, я поместил код в GitHub gist