使用lpSolveAPI获得针对0/1-背包MILP的多种解决方案 [英] Get multiple solutions for 0/1-Knapsack MILP with lpSolveAPI
问题描述
可复制的示例:
我描述了一个简单的 0/1-背包问题,其中包含 R ,它应该返回2个解决方案:
I described a simple 0/1-Knapsack problem with lpSolveAPI in R, which should return 2 solutions:
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
解决方案:
But get.solutioncount(lp_model)
shows that there's just 1
solution found:
> 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
我希望有两种解决方案:1 0 1
和0 1 1
.
I would expect that there are 2 solutions: 1 0 1
and 0 1 1
.
我尝试传递 lpSolve num.bin.solns参数. >与solve(lp_model, num.bin.solns=2)
,但解决方案的数量仍为1
.
I tried to pass the num.bin.solns
argument of lpSolve with solve(lp_model, num.bin.solns=2)
, but the number of solutions remained 1
.
问题:
如何获得两个正确的解决方案? 我更喜欢使用 lpSolveAPI ,因为该API非常好. 如果可能的话,我想避免直接使用 lpSolve .
How can I get the two correct solutions? I prefer using lpSolveAPI as the API is really nice. If possible I'd like to avoid to use lpSolve directly.
推荐答案
看起来像坏了.这是您特定模型的DIY方法:
Looks like that is broken. Here is a DIY approach for your specific model:
# 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
这个想法是通过添加一个约束来切断当前的整数解.然后解决.当不再最佳时或目标开始恶化时停止. 此处是一些数学背景.
The idea is to cut off the current integer solution by adding a constraint. Then resolve. Stop when no longer optimal or when the objective starts to deteriorate. Here is some math background.
您现在应该看到:
> sols
[[1]]
[1] 1 0 1
[[2]]
[1] 0 1 1
更新
在下面的评论中,有人问为什么切口系数的形式为 2 * sol-1 .再次查看推导.这是一个反例:
Below in the comments it was asked why coefficients of the cut have the form 2*sol-1. Again have a look at the derivation. Here is a counter example:
C1 C2
Maximize 0 10
R1 1 1 <= 10
Kind Std Std
Type Int Int
Upper 1 1
Lower 0 0
使用我的"切割将产生:
With "my" cuts this will yield:
> sols
[[1]]
[1] 0 1
[[2]]
[1] 1 1
在使用建议的错误"切割时,只会给出:
while using the suggested "wrong" cuts will give just:
> sols
[[1]]
[1] 0 1
这篇关于使用lpSolveAPI获得针对0/1-背包MILP的多种解决方案的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!