多维背包的启发式

Question

这是以下问题的后续问题：鉴于上一个问题在合理的时间内解决了（优化）大小 <= 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 数组所示。

我当前的解决方案（) uses dynamic programming and works for small problems. I have seen heuristics involving dynamic programming, such as https://youtu.be/ze1Xa28h_Ns，但无法弄清楚如何将其应用于多维问题。鉴于问题的限制，应用什么是合理的启发式方法？

编辑：我尝试过的事情

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

Answer 1

一个合理的启发式算法（我想到的第一个）应该是迭代地采用得分最高的可行元素，消除所有与所选元素有重叠位的元素。

我会通过首先按分数降序排序然后迭代添加第一个元素并过滤列表，删除与所选元素重叠的任何元素来实现此目的。

在javascript中：

function comp(a, b) {
  if (a[1] < b[1]) return 1;
  if (a[1] > b[1]) return -1;
  return 0;
}
S.sort(comp);  // Sort descending by score

var output = []
var score = 0;
while (S.length > 0) {
  output.push(S[0][0]);
  score += S[0][1];
  newS = [];
  for (var i=0; i < S.length; i++) {
    if ((S[i][0] & S[0][0]) == 0) {
      newS.push(S[i]);
    }
  }
  S = newS;
}

alert(JSON.stringify([output, score]));

这将选择元素 7、8 和 16，得分为 179（相对于最佳得分 180）。

Answer 2

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

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 and glpk.js and 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 包来执行此操作），你可以在到达你的之前获得求解器找到的最佳解决方案指定超时。这可能不是最佳解决方案，您可以控制启发式停止尝试寻找更好解决方案的时间。如果求解器在超时前终止，则保证解决方案是最优的。

多维背包的启发式

Heuristic for multi-dimensional knapsack

javascript

algorithm

knapsack-problem

mathematical-optimization

dynamic-programming