r - 在 R (Rglpk?) 中使用线性规划找到所有可能的解决方案

Question

我很乐意在 R 中使用 Rglpk 找到最佳解决方案，但是，我正在努力寻找解决方案是生成满足最低标准值的所有可能解决方案。

例如，对于下面的基本数据框，我可以使用 Rglpk 找到 1 男 1 女的最佳总结果。

df<-data.frame(c("John","Sandy","James","Sharon"),c("M","F","M","F"),c(84,70,13,62))
colnames(df)<-c("Name","Sex","Result")

df
    Name Sex Result
1   John   M     84
2  Sandy   F     70
3  James   M     13
4 Sharon   F     62

library(Rglpk)
num <- length(df$Name)
obj<-df$Result
var.types<-rep("B",num)
matrix <- rbind(as.numeric(df$Sex == "M"),as.numeric(df$Sex == "F"))
direction <- c("==","==")
rhs<-c(1,1)
sol <- Rglpk_solve_LP(obj = obj, mat = matrix, dir = direction, rhs = rhs,types = var.types, max = TRUE)

df[sol$solution==1,]
   Name Sex Result
1  John   M     84
2 Sandy   F     70

但是，如果我想找到该数据框的所有可能解决方案或“组合”，其中 1 名男性和 1 名女性得分的组合结果超过 140，我无法弄清楚如何生成此解决方案并随后按以下方式进行格式化

     M      F Result
1 John  Sandy    154
2 John Sharon    146

将不胜感激人们可以提供的任何帮助。

Answer 1

您可以使用以下算法:

解决MIP

如果不可行:停止

向模型添加禁止当前最优解的约束。

转到步骤 1。

步骤 3 中的约束可能如下所示:

sum(i, a(i)*x(i)) - sum(i, (1-a(i))*x(i)) <= sum(i, a(i)) - 1

哪里 a(i)是当前的最优解(在步骤 1 中找到)。 IE。 a(i) = x*(i) . a在这里是常数。请注意，每个循环中约束的数量增加一个(因此模型变得越来越大)。

这是此切割的推导: link .

看起来您仍然需要添加一个约束以确保分数超过 140。