r - 在 lpSolveAPI R 中添加计数约束

Question

我正在尝试深入优化，并且一直在摆弄 lpSolveAPI 包。示例将演示我的简单设置。

数据(每行保存不同的变量):

dput(test.df)
    structure(list(objective = c(-0.162235888601422, -0.168597233981057, 
    -0.165558234725657, -0.156096491294958, -0.15294764940114), constrain1 = c(1.045, 
    1.259, 1.792, 2.195, 2.802)), .Names = c("objective", "constrain1"
    ), row.names = c(NA, -5L), class = "data.frame")

library(lpSolveAPI)

创建空模型，包含 5 个变量(test.df 中的行)，我想最大化我的目标。

test.lp <- make.lp(0, NROW(test.df))
set.objfn(test.lp, test.df$objective)
lp.control(test.lp,sense='max')

让我们添加一些约束。

add.constraint(test.lp, test.df$constrain1, "=", 2)
add.constraint(test.lp, rep(1, nrow(test.df)), "=", 1)
set.bounds(test.lp, upper = rep(0.5, nrow(test.df)))
set.bounds(test.lp, lower = rep(0, nrow(test.df)))
RowNames <- c("constraint1", "constraint2")
ColNames <- paste0("var", seq(1, nrow(test.df)))
dimnames(test.lp) <- list(RowNames, ColNames)

我想创建一个约束，即在求解中仅使用 x 个变量。因此，如果我将其设置为 2，它将使用其中 2 个变量创建最佳解决方案。我尝试过 set.type = "binary" 但没有成功。

Answer 1

我认为你想添加一个约束，将非零变量 x(i) 的数量限制为 2。计数实际上不能在 LP 中完成，但可以将其表示为 MIP .

标准公式是引入二元变量y(i):

x(i) <= y(i)*xup(i)      (implication: y(i)=0 => x(i)=0)
sum(i, y(i)) <= 2     
0 <= x(i) <= xup(i)      (bounds)
y(i) in {0,1}            (binary variables) 

对于较大的问题，这比解决每种可能的组合要有效得多。虽然 N 中的 k=2 并没有那么糟糕:N 选择 k = N*(N-1)/2 可能的组合。