r - 给定某些约束条件 R 选择大小为 k 的最优子集

Question

我在 R 中有一个 data.table，大小为 100K 行和 6 列(假设 x_1, ... x_6)。

我正在寻找大小为 1K 行的子集，以便优化(可能不是最佳的，但至少比随机或排序更好)如何选择这千行并优化 a*sum(x_1) + ... + f*sum(x_6)，其中 a,...,f 是数字。

有没有使用算法/库来解决这个问题的建议？

谢谢!

可重现的例子:

# Creation of sinthetic data
set.seed(123)
total <- data.frame(id = 1:1000000, x1 =  runif(1000000,0,1),  x2 =  60*runif(100000,0,1), 
                    x3 = runif(100000,0,1), x4 = runif(1000000,0,1), Last_interaction = sample(1:35, 1000000, replace= T))

total$x3 <- -total$x2 * total$x3 * runif(100000,0.7,1)
head(total)

# We are looking for a subset of 1000 rows such that
Cost_function <- function(x1,x2,x3,x4)
{
  0.2*max(x1) + 0.4*sum(x2) - 0.3*sum(x2) - 0.1*max(x4)
}
# is maximized.

# We rank the dataset by weights in cost function
total <- total[with(total, order(-x2, x3,-x1,-x4)), ]
head(total)

# Want to improve (best choice by just ranking and getting top1000) 
result_1 <- total[1:1000,]
# And of course random selection
result_2 <- total[sample(1:nrow(total), 1000,
                          replace=FALSE),]


# Wanna improve sorting and random selection if possible
Cost_function(result_1$x1,result_1$x2,result_1$x3,result_1$x4)
# [1] 5996.787
# (high value, but improvable)
Cost_function(result_2$x1,result_2$x2,result_2$x3,result_2$x4)
# [1] 3000
# low performace

Answer 1

这是一个奇怪的成本函数:0.2*max(x1) + 0.4*sum(x2) - 0.3*sum(x2) - 0.1*max(x4).. 我不知道认为所提出的计算 Ax 的方法(随后进行排序)与此相对应。成本函数中 max 和 sum 的组合使其在行中不可分离，因此我们不能只使用排序。我唯一能想出的是 MIP 公式(一个二进制变量，指示是否选择了一行)。

该模型并非完全平凡:

参见 here了解详情。

对于小型数据集，它执行以下操作:

请注意，另一个答案(现已删除)中给出的 LP 模型是不正确的(即使对于所有正值也是如此)。为非凸情况正确建模 max 并非易事。