Optaplanner - 拥有数百万行的大型数据集

Question

有几条线程讨论Optaplanner的可伸缩性，我想知道在涉及数百万行时处理大型数据集的建议方法是什么？

正如本博客讨论我已经使用启发式（模拟退火+禁忌搜索）。云平衡问题的搜索空间为c^p，但可行空间为未知/ NP-complete。

http://www.optaplanner.org/blog/2014/03/27/IsTheSearchSpaceOfAnOptimizationProblemReallyThatBig.html

我试图解决的问题是类似云平衡。但主要的区别在于输入数据，除了计算机列表和进程列表之外，还有一个很大的二维“分数列表/表格”，它具有需要加载到内存中的每种可能组合的分数。

换句话说，除了计划和流程之间的规则需要满足的限制外，不同的有效组合产生不同的分数，分数越高越好。

这是一个简单的问题，但对于数百台电脑，100k +进程和分数表有百万个组合，它需要大量的内存。尽管我可以分配更多内存来增加堆大小，但由于这些步骤是使用自定义计划变量/实体比较器类进行排序的，因此规划可能会变得非常缓慢并且很困难。

一个直接的解决方案是将数据集分成更小的子集，分别运行它们，然后合并结果，这样我就可以同时运行多台机器，并且每台机器都运行在多线程。这种方法的最大缺点是产生的结果远离最优。

我想知道还有其他更好的解决方案吗？

Answer 1

MachineReassignment示例还有一个很大的“分数组合”矩阵。 OptaPlanner不关心这些 - 这些只是问题的事实，DRL可以快速匹配选择的组合。 Solver.solve()不会导致大的内存消耗或性能影响。 然而，在你的代码加载问题（主叫Solver.solve()前）做造成巨大的内存消耗：明白，如果n = 20k，然后n² = 400m和int需要的4个字节，所以20 000元素矩阵1.6 GB以其最有效的非压缩形式int[][]（都在Java和C++中！）。因此，对于20k备用2GB RAM，对于80k备用32 GB RAM的40k备用8GB RAM。这个规模很大。

至于处理这些大问题，我使用的技术组合如附近的选择（请参阅我的博客文章），分区搜索（你所描述的，它将支持开箱即用7，但我已经在CustomPhase中为客户实现了它），有限的选择构建启发式（需要进一步研究，管道存在，通常是矫枉过正）......分区搜索确实排除了最优解决方案，但是超过10k个规划实体，关闭质量与时间明显有利分区搜索给予合理的解决时间（分钟/小时/天而不是千年）。诀窍是保持每个分区的大小足够大，超过1k个实体（因此使用NearbySelection）。当然，分数计算速度也很重要。