使用 lpSolveAPI 获取 0/1-Knapsack MILP 的多个解决方案
Get multiple solutions for 0/1-Knapsack MILP with lpSolveAPI
可重现示例:
我描述了一个简单的0/1-Knapsack problem with lpSolveAPI in R,应该return2个解决方案:
library(lpSolveAPI)
lp_model= make.lp(0, 3)
set.objfn(lp_model, c(100, 100, 200))
add.constraint(lp_model, c(100,100,200), "<=", 350)
lp.control(lp_model, sense= "max")
set.type(lp_model, 1:3, "binary")
lp_model
solve(lp_model)
get.variables(lp_model)
get.objective(lp_model)
get.constr.value((lp_model))
get.total.iter(lp_model)
get.solutioncount(lp_model)
问题:
但是 get.solutioncount(lp_model)
表明只找到了 1
个解决方案:
> lp_model
Model name:
C1 C2 C3
Maximize 100 100 200
R1 100 100 200 <= 350
Kind Std Std Std
Type Int Int Int
Upper 1 1 1
Lower 0 0 0
> solve(lp_model)
[1] 0
> get.variables(lp_model)
[1] 1 0 1
> get.objective(lp_model)
[1] 300
> get.constr.value((lp_model))
[1] 350
> get.total.iter(lp_model)
[1] 6
> get.solutioncount(lp_model)
[1] 1
我希望有 2 个解决方案:1 0 1
和 0 1 1
。
我尝试用solve(lp_model, num.bin.solns=2)
传递lpSolve的num.bin.solns
参数,但解数仍然是1
。
问题:
我怎样才能得到两个正确的解决方案?
我更喜欢使用 lpSolveAPI,因为 API 非常好。
如果可能的话,我想避免直接使用 lpSolve 。
看起来好像坏了。这是针对您的特定型号的 DIY 方法:
# first problem
rc<-solve(lp_model)
sols<-list()
obj0<-get.objective(lp_model)
# find more solutions
while(TRUE) {
sol <- round(get.variables(lp_model))
sols <- c(sols,list(sol))
add.constraint(lp_model,2*sol-1,"<=", sum(sol)-1)
rc<-solve(lp_model)
if (rc!=0) break;
if (get.objective(lp_model)<obj0-1e-6) break;
}
sols
思路是通过加一个约束来截断当前的整数解。然后解决。当不再最优或 objective 开始恶化时停止。 Here 是一些数学背景。
你现在应该看到:
> sols
[[1]]
[1] 1 0 1
[[2]]
[1] 0 1 1
更新
下面的评论中有人问为什么切割的系数具有 2*sol-1 的形式。再看看 the derivation。这是一个反例:
C1 C2
Maximize 0 10
R1 1 1 <= 10
Kind Std Std
Type Int Int
Upper 1 1
Lower 0 0
使用 "my" 削减将产生:
> sols
[[1]]
[1] 0 1
[[2]]
[1] 1 1
使用建议的 "wrong" 削减只会得到:
> sols
[[1]]
[1] 0 1
可重现示例:
我描述了一个简单的0/1-Knapsack problem with lpSolveAPI in R,应该return2个解决方案:
library(lpSolveAPI)
lp_model= make.lp(0, 3)
set.objfn(lp_model, c(100, 100, 200))
add.constraint(lp_model, c(100,100,200), "<=", 350)
lp.control(lp_model, sense= "max")
set.type(lp_model, 1:3, "binary")
lp_model
solve(lp_model)
get.variables(lp_model)
get.objective(lp_model)
get.constr.value((lp_model))
get.total.iter(lp_model)
get.solutioncount(lp_model)
问题:
但是 get.solutioncount(lp_model)
表明只找到了 1
个解决方案:
> lp_model
Model name:
C1 C2 C3
Maximize 100 100 200
R1 100 100 200 <= 350
Kind Std Std Std
Type Int Int Int
Upper 1 1 1
Lower 0 0 0
> solve(lp_model)
[1] 0
> get.variables(lp_model)
[1] 1 0 1
> get.objective(lp_model)
[1] 300
> get.constr.value((lp_model))
[1] 350
> get.total.iter(lp_model)
[1] 6
> get.solutioncount(lp_model)
[1] 1
我希望有 2 个解决方案:1 0 1
和 0 1 1
。
我尝试用solve(lp_model, num.bin.solns=2)
传递lpSolve的num.bin.solns
参数,但解数仍然是1
。
问题:
我怎样才能得到两个正确的解决方案? 我更喜欢使用 lpSolveAPI,因为 API 非常好。 如果可能的话,我想避免直接使用 lpSolve 。
看起来好像坏了。这是针对您的特定型号的 DIY 方法:
# first problem
rc<-solve(lp_model)
sols<-list()
obj0<-get.objective(lp_model)
# find more solutions
while(TRUE) {
sol <- round(get.variables(lp_model))
sols <- c(sols,list(sol))
add.constraint(lp_model,2*sol-1,"<=", sum(sol)-1)
rc<-solve(lp_model)
if (rc!=0) break;
if (get.objective(lp_model)<obj0-1e-6) break;
}
sols
思路是通过加一个约束来截断当前的整数解。然后解决。当不再最优或 objective 开始恶化时停止。 Here 是一些数学背景。
你现在应该看到:
> sols
[[1]]
[1] 1 0 1
[[2]]
[1] 0 1 1
更新
下面的评论中有人问为什么切割的系数具有 2*sol-1 的形式。再看看 the derivation。这是一个反例:
C1 C2
Maximize 0 10
R1 1 1 <= 10
Kind Std Std
Type Int Int
Upper 1 1
Lower 0 0
使用 "my" 削减将产生:
> sols
[[1]]
[1] 0 1
[[2]]
[1] 1 1
使用建议的 "wrong" 削减只会得到:
> sols
[[1]]
[1] 0 1