寻找一个模型来表示这个问题，我怀疑这个模型可能是NP-完全的。

Question

(我改变了这个问题的细节，以避免NDA问题。我知道，如果从字面上看，有更好的方法来经营这个理论公司。)

有一组仓库，每个仓库都可以储存和分发200种不同的产品，而A公司生产的产品总数可能有1000种。每个仓库都储存了200种产品，并分配了订单，然后他们将从手头的库存中填补这些订单。

挑战在于每个仓库都需要自给自足。将有一个任意数量的产品(通常为5-10)的订单，这是分配给一个仓库。然后仓库为订单包装所需的产品，并将它们一起装运。对于任何在仓库中不可用的物品，在定单发运之前，必须将物品单独送到仓库。

因此，问题在于确定最佳的仓库/产品配置，以便可以包装尽可能多的订单，而不必订购和等待单个项目。

例如(使用由字母表示的产品和能够储存5条产品线的仓库)：

Warehouse 1: [A, B, C, D, E]
Warehouse 2: [A, D, F, G, H]

Order: [A, C, D] -> Warehouse 1
Order: [A, D, H] -> Warehouse 2
Order: [A, B, E, F] -> Warehouse 1 (+1 separately ordered)
Order: [A, D, E, F] -> Warehouse 2 (+1 separately ordered)

我们的目标是使用历史数据来减少未来个别订购产品的数量。一旦建立了一定的仓库，软件就可以确定哪个仓库可以以最小的开销处理订单。

这立刻让我觉得这是一个机器学习风格的问题。这似乎也是一些众所周知的NP-完全问题的组合，尽管它们似乎都不适合。

是否有代表这类问题的模型？

Answer 1

如果我理解正确的话，你必须把问题分开：

• 预测每个仓库应该预购什么？
• 为订单找到最好的仓库

对于第一个问题，我向您指出netflix奖：这是几乎相同的问题，并且已经提出了很好的解决方案。(我的数据收集手册在家里，我不记得谷歌的准确关键词，sorry.Try“数据挖掘时间序列”)

对于第二个问题，这是Prolog的一个问题。

• 设置单独订购项目的成本
• 设置一个成本，因为，距离客户很近。
• 将已经拥有该产品的成本设置为0。
• 制定获得产品的规则:如果你没有，就买它，如果你买了，就买它。
• 制定获得所有产品的规则:前面的产品，上面的规则
• 获取此规则的成本
• 轻轻地让Prolog找到一个解决方案。如果还不够好，就多问几句。

如果您不想使用Prolog，那么有几个约束库。只是谷歌“约束库<insert your programming language here”

Answer 2

问题的第一部分(经常将项目排序在一起)有时被称为共现问题，是数据挖掘文献中的一个重要部分。(我记得这个问题在NP中，但是有相当好的近似算法)。

一旦你有了你满意的共现数据，你仍然会被分配到仓库的物品。有点像套盖问题，但不完全一样。这个问题很难解决.