r - 使用 lpSolveAPI 获取 0/1-Knapsack MILP 的多个解决方案

Question

可重现示例:

我描述了一个简单的0/1-Knapsack lpSolveAPI 的问题在 R ，它应该返回 2 个解决方案:

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。

我尝试传递 lpSolve 的 num.bin.solns 参数使用 solve(lp_model, num.bin.solns=2)，但解数仍为 1。

问题:

怎样才能得到这两个正确的解呢？我更喜欢使用lpSolveAPI因为 API 真的很好。如果可能的话我想避免使用 lpSolve直接地。

Answer 1

看起来好像坏了。以下是针对您的特定型号的 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

这个想法是通过添加约束来切断当前的整数解。然后解决。当不再最佳或目标开始恶化时停止。 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       

通过“我的”削减，这将产生:

> sols
[[1]]
[1] 0 1

[[2]]
[1] 1 1

当使用建议的“错误”切割时，只会给出:

> sols
[[1]]
[1] 0 1