r - 如何使用 LpSolve 在 R 中设置线性规划优化？

Question

例如，我有这个示例数据:

d=data.frame(x=c(1,1,1,2,2,3,4,4),y=c(5,6,7,8,7,5,6,5),w=c(1,2,3,4,5,6,7,8))

看起来像这样:

  x y w
1 1 5 1
2 1 6 2
3 1 7 3
4 2 8 4
5 2 7 5
6 3 5 6
7 4 6 7
8 4 5 8

x和 y表示来自 datax 的索引和 datay . w表示通过比较得到的分数 datax[x]与 datay[y] .我想最大化来自 w 的总分(或 d ) ，其中每个值 x最多匹配一个值 y ，反之亦然。

结果应如下所示:

  x y w
1 2 7 5
2 3 5 6
3 4 6 7

凡总和 w值被最大化，每个 x和每个 y结果中只出现一次。

我如何在 lpSolve::lp 中设置此问题功能？

Answer 1

您可以使用 lpSolveAPI 来解决您的问题。鉴于您的限制，您所述的解决方案不太可行。所以让我们和你一起去，希望 X 和 Y 不在解决方案中重复。
您将需要 8 个新的二进制变量。每个变量指定该行是否在 d 中被选中 (1) 或被丢弃 (0)。
根据 OP 的要求更新
是的，lpSolveAPI 代码(如下)使它看起来比实际更复杂。这个 LP 公式(lpSolveAPI 的输出)应该让事情更清楚:

/* Objective function */
max: +pick_1 +2 pick_2 +3 pick_3 +4 pick_4 +5 pick_5 +6 pick_6 +7 pick_7 +8 pick_8;

/* Constraints */
OneX_1: +pick_1 +pick_2 +pick_3 <= 1;
OneX_2: +pick_4 +pick_5 <= 1;
OneX_4: +pick_7 +pick_8 <= 1;
OneY_5: +pick_1 +pick_6 +pick_8 <= 1;
OneY_6: +pick_2 +pick_7 <= 1;
OneY_7: +pick_3 +pick_5 <= 1;

/* Variable bounds */
pick_1 <= 1;
pick_2 <= 1;
pick_3 <= 1;
pick_4 <= 1;
pick_5 <= 1;
pick_6 <= 1;
pick_7 <= 1;
pick_8 <= 1;

说明:第二个约束 (OneX_2) 只是声明 pick_4 中只有一个或 pick_5可以是 1，因为数据帧中的第 4 行和第 5 行 d有 X = 2
解决方案
请注意，上面的公式产生了一个最佳解决方案，该解决方案在数据帧 d 中选择了 4 行。

> d[c(3,4,6,7),]
  x y w
3 1 7 3
4 2 8 4
6 3 5 6
7 4 6 7

w 的总和为 20，这比问题中的解决方案要好。
代码

library(lpSolveAPI)
d <- data.frame(x=c(1,1,1,2,2,3,4,4),y=c(5,6,7,8,7,5,6,5),w=c(1,2,3,4,5,6,7,8))

ncol <- 8 #you have eight rows that can be picked or dropped from the solution set
lp_rowpicker <- make.lp(ncol=ncol)
set.type(lp_rowpicker, columns=1:ncol, type = c("binary"))

obj_vals <- d[, "w"]
set.objfn(lp_rowpicker, obj_vals) 
lp.control(lp_rowpicker,sense='max')

#Add constraints to limit X values from repeating
add.constraint(lp_rowpicker, xt=c(1,1,1), #xt specifies which rows of the LP
               indices=c(1,2,3), rhs=1, type="<=")
add.constraint(lp_rowpicker, xt=c(1,1), #xt specifies which rows of the LP
               indices=c(4,5), rhs=1, type="<=")
add.constraint(lp_rowpicker, xt=c(1,1), #xt specifies which rows of the LP
               indices=c(7,8), rhs=1, type="<=") #x's in dataframe rows 7 & 8 are both '4'

#Add constraints to limit Y values from repeating
add.constraint(lp_rowpicker, xt=c(1,1,1), #xt specifies which rows of the LP
               indices=c(1,6,8), rhs=1, type="<=") #Y's in df rows 1,6 & 8 are all '5'
add.constraint(lp_rowpicker, xt=c(1,1), #xt specifies which rows of the LP
               indices=c(2,7), rhs=1, type="<=") #Y's in dataframe rows 2&7 are both '6'
add.constraint(lp_rowpicker, xt=c(1,1), #xt specifies which rows of the LP
               indices=c(3,5), rhs=1, type="<=") #y's in dataframe rows 3&5 are both '7'

solve(lp_rowpicker)
get.objective(lp_rowpicker) #20
get.variables(lp_rowpicker)
#[1] 0 0 1 1 0 1 1 0
#This tells you that from d you pick rows: 3,4,6 & 7 in your optimal solution.

#If you want to look at the full formulation:
rownames1 <- paste("OneX", c(1,2,4), sep="_")
rownames2 <- paste("OneY", c(5,6,7), sep="_")
colnames<- paste("pick_",c(1:8), sep="")
dimnames(lp_rowpicker) <- list(c(rownames1, rownames2), colnames)
print(lp_rowpicker)

#write it to a text file
write.lp(lp_rowpicker,filename="max_w.lp")

希望这能让您了解如何使用 lpSolveAPI 来制定您的问题。