최대 값의 벡터를 초과하지 않는 최적의 그룹으로 숫자를 결합하는 알고리즘?

Question

저는 집의 트림 몰딩을 자르고 다양한 길이의 트림 조각을 가지고 있으며 가장 적은 양의 낭비를 위해 최적으로 그룹화하려고합니다. 기본적으로, 필자는 필요한 길이를 가능한 긴 길이로 최적 그룹화 (또는 팩)하려고합니다.

나는이 문제에 접근하는 방법에 다소 혼란 스럽지만 현재는 손으로 직접하고있다. 그러나 실수로 인해 전체 작업을 다시해야한다. 나는 몇몇 Java를 알고 있지만, 최근에 R로 exlusively 작업을 해왔다. 그래서 나는이 시점에서 나의 가장 친숙한 언어이다. 이 접근 방법에 대한 제안이 있습니까?

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 벡터의 "outside in"을 확인하고 있습니다. 손으로 만든 페어링은 종종 작고 중간 수준의 값을 사용하기 쉬운 길이로 페어링하여 꽤 쉽게 볼 수 있습니다. 쌍을 이루는 것보다

어쨌든, 그것은 흥미로운 문제 였고 해결책이 있는지를 알기위한 참고 자료 나 분명한 제안이 있는지 궁금해했습니다. 일부 관련 질문에서 첫 번째 의견은 종종 "무엇을 시도 했습니까?"라고 물었습니다. 나는 진짜로 ... 나는 지금 당황하다. 내가 생각한 단 한가지는 조합을 무작위로 강제로 조합하여 낭비를 최소화하는 솔루션을 저장하는 것뿐이었습니다.

나는 이것을 벡터화 된 방법으로 해결하는 것에 대한 몇 가지 제안 - 어떤 종류의 행렬 연산 또는 문제의 선형 모델 표현을 좋아할 것입니다. 나는 그것에 대해서도 계속 생각할 것이다.

Answer 1

예의http://xkcd.com/287/

(예,이 코멘트가 아닌 답변입니다. 단지 imgs가 작은 작은 주석 행에로드 할 수있는 경우)

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을 필요한 트림 길이로합시다.

• 변수 : t 트림 경우 하자 1 일 X_a_t는이 아니면 0

A_I 마이너스 J = 1..N 위에 합계로 Surplus_i 정의 가능한 부분 로부터 잘라 의 (X_a_t *의 t_j)

• 목적 : 모든 A의 (1..k)에 대한 Surplus_i의 합을 최소화

,691 363,210

제약이

• 세트의 파티션 제약 (영어) 모든 트림은 일부 조각 또한

  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