javascript - 多维背包的启发式

Question

这是一个后续问题:Finding max value of a weighted subset sum of a power set 鉴于上一个问题在合理的时间内解决了(优化)大小 <= 15 的问题，我想解决大小为 ~2000 的问题以接近优化。

作为一个小示例问题，我得到了一定范围的节点:

var range = [0,1,2,3,4];

一个函数为范围内的所有节点创建一个幂集，并为每个组合分配一个数字分数。负分被删除，生成以下数组 S。 S[n][0] 是所有包含节点的按位或，S[n][1] 是分数:

var S = [
  [1,0], //0
  [2,0], //1
  [4,0], //2
  [8,0], //3
  [16,0], //4
  [3,50], //0-1 
  [5,100], //0-2
  [6,75], //1-2
  [20,130], //2-4
  [7,179] //0-1-2 e.g. combining 0-1-2 has a key of 7 (bitwise `1|2|4`) and a score of 179.
];

最大化得分的最佳解决方案是:

var solution = [[8,3,20],180]

其中 solution[0] 是来自 S 的组合数组。 solution[1] 是结果分数。请注意，按位 8 & 3 & 20 == 0 表示每个节点仅使用一次。

问题细节:每个节点必须恰好使用一次，单节点组合的分数将始终为 0，如上面的 S 数组所示。

我当前的解决方案 ( seen here ) 使用动态规划并适用于小问题。我见过涉及动态规划的启发式算法，例如 https://youtu.be/ze1Xa28h_Ns ，但无法弄清楚如何将其应用于多维问题。给定问题约束，应用什么是合理的启发式方法？

编辑: 我尝试过的事情

• 贪心法(将 score 从大到小排序，选择下一个可行的候选人)
• 同上，但按score/cardinality(combo)排序
• GRASP(将每个 score 最多编辑 10%，然后排序，重复直到在 x 秒内没有找到更好的解决方案)

Answer 1

这个问题实际上是一个整数优化问题，二进制变量 x_i 表示是否选择了 S 的第 i^th 个元素和约束表示每个位只使用一次。目标是最大化所选元素的得分。如果我们将 S_i 定义为 S 的第 i^ 个元素，则 L_b 为元素的索引S 位 b 设置，w_i 是与元素 i 关联的分数，并假设有 n 个元素在集合 S 和 k 位中，我们可以用数学符号将其写为:

min_{x} \sum_{i=1..n} w_i*x_i
s.t.    \sum_{i \in L_b} x_i = 1  \forall b = 1..k
        x_i \in {0, 1}            \forall i = 1..n

在许多情况下，线性规划求解器在解决此类问题时比穷举搜索更有效(很多很多)。不幸的是，我不知道有任何 javascript 线性编程库(Google 查询出现了 SimplexJS 和 glpk.js 和 node-lp_solve ——我没有任何这些方面的经验，无法立即让任何工作)。因此，我将使用 lpSolve 包在 R 中实现。

w <- c(0, 0, 0, 0, 0, 50, 100, 75, 130, 179)
elt <- c(1, 2, 4, 8, 16, 3, 5, 6, 20, 7)
k <- 5
library(lpSolve)
mod <- lp(direction = "max",
          objective.in = w,
          const.mat = t(sapply(1:k, function(b) 1*(bitwAnd(elt, 2^(b-1)) > 0))),
          const.dir = rep("=", k),
          const.rhs = rep(1, k),
          all.bin = TRUE)
elt[mod$solution > 0.999]
# [1]  8  3 20
mod$objval
# [1] 180

您会注意到，这是您的问题的精确表述。但是，通过设置超时(您实际上需要使用 R 中的 lpSolveAPI 包而不是 lpSolve 包来执行此操作)，您可以获得找到的最佳解决方案在达到您指定的超时之前由求解器执行。这可能不是最佳解决方案，您可以控制启发式停止尝试寻找更好解决方案的时间。如果求解器在超时前终止，则保证解是最优的。