2

我有一个带有线性约束的简单 LP。有很多决策变量，大约 2400 万个。我一直在 R 中使用 lpSolve 来处理小样本，但是这个求解器不能很好地缩放。有没有办法得到 LP 的近似解？

编辑：

问题是调度问题。有 100 万人需要安排到 24 小时之一，因此有 2400 万个决策变量。将人 $i$ 安排到小时 $j$ 有奖励 $R_{ij}$。约束是每个人都需要被安排到某个小时，但每个小时只有有限数量的预约空档 $c$

4

2 回答 2

3

处理具有大量变量和约束的 LP/IP 的一种好方法是寻找以某种逻辑方式对决策变量进行分组的方法。由于您只给出了问题的草图，因此这里有一个解决方案的想法。

方法 1：将人员分成更小的批次

不要把 100 万人想象成 100 个单位，每个单位有 10000 人。所以现在你只有 2400 (24 x 100) 个变量。这将使您成为其中的一部分，并注意这不是最佳解决方案，而是一个很好的近似值。你当然可以做1000批1000人，得到更细粒度的解决方案。你明白了。

方法 2：根据成本分组

看看你的 R_ij 的。大概你没有一百万种不同的成本。通常只有几个独特的成本值。这个想法是将许多具有相同成本结构的人组合成一个“队列”。现在你解决了一个小得多的问题——哪些队列进入了哪个小时。

同样，一旦你有了这个想法，你就可以让它变得非常容易处理。

更新基于 OP 的评论：就其本质而言，制作这些组是一种近似技术。无法保证会获得最佳解决方案。然而，仔细分组的整个想法（通过查看具有相同或非常相似的成本结构的群组）是为了获得尽可能接近最优的解决方案，而计算工作量要少得多。

  • 我还应该补充一点，当缩放时（分组只是缩小问题大小的一种方法），其他常数也应该被缩放。也就是说，c_j 也应该是相同的单位（10K）。
  • 如果人 A,B,C 不能适应时间槽 j，那么模型将尽可能多地挤入成本最低的时间槽中，并将其他人移动到成本稍高的其他时间槽，但他们可以容纳。

希望这可以帮助您朝着正确的方向前进。

于 2013-04-24T16:24:50.793 回答
2

假设您有很多重复的人，那么您现在使用的变量太多了。

假设你只有 1000 种不同的人，其中一些人出现了 2000 次，而另一些人出现了 500 次。

然后你只需要优化你每小时分配的人的比例。（请注意，您必须通过添加 2000 或 500 作为常数来稍微调整目标函数和约束）

好消息是，这应该为您提供仅包含“几个”变量的最佳解决方案，但根据您的问题，您可能需要对结果进行四舍五入以获得整个人作为结果。

于 2013-04-24T16:36:04.697 回答