尝试使用这个multiple-knapsack问题似乎很有趣lpSolveAPI，这就是我所做的。我使用整数编程方法来找到修剪问题的最佳解决方案。
首先，这是我找到的解决方案的样子：
如您所见，有 5 个可用部件根本不需要。（100% 盈余）
公式
- 设 a_1, a_2, ..., a_k 为可用的片长。
令 t_1, t_2, ..., t_n 为所需的修剪长度。
变量：如果修剪t是从可用片a中切割出来的，则令 X_a_t 为 1 ，否则为 0
将 Surplus_i 定义为 A_i 减去 (X_a_t * t_j) 的 j=1..n 的总和
- 目标：最小化所有 A (1..k) 的 Surplus_i 的总和
约束
此外，所有盈余必须 >= 0 # 不允许负数
A_i - sum over j in 1..k X_ai_tj * t_j = Surplus_i (for each Ai) # definitional constraint.
使用 lpSolveAPI 的 R 代码
在我的 A 矩阵中（第一组列是剩余变量，下一组是 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
由