algorithm - 将 M 个实验分配给 N 个实验室，同时遵守约束条件

Question

我有以下问题:我必须将 K 个实验分配给 N 个实验室，同时遵守一些一般约束和一些特定约束。

一般的有:

1. 每个实验必须恰好分配给 R 个实验室
2. 每个实验室的实验数量上限为 M
3. 理想情况下，每个实验室的实验分布接近均匀(但可以稍微放松)
4. 没有遗漏任何实验室

然后是具体的限制条件。由于并非所有实验室都拥有相同的设备和试剂，因此每个实验室都会有自己的一套他们不能/不能进行的实验。

在我看来，这是一个满足约束的问题。我知道它们存在，但我没有使用它们的经验。

我想知道是否有一种方法可以通过将其映射到已知图问题或存在足够好的算法的其他问题来解决此问题，或者，如果失败，是否有优化搜索的方法，如果需要被暴力破解。

谢谢!

Answer 1

其中很大一部分可以表述为最大流问题。也就是说，准备一个包含源、实验节点、实验室节点和汇的流网络。从源到每个实验节点放一条容量 R 的弧。从每个实验室节点到汇点放置一条容量 M 的弧。将容量 1 的弧从每个实验节点到每个实验室节点，以便该实验室可以执行该实验。给定一个使来自源的所有弧饱和的积分流(如果存在，这将是最大流)，每个具有流的实验室到实验弧都是一个指定的实验。

这满足 1 和 2 以及哪些实验室可以执行哪些实验的具体限制。我希望您可以调整 M 以满足约束 3 和 4，但如果不能，您可以将公式扩展为更一般的整数规划，并在实验分布方面增加额外约束。

(实际上，经过深思熟虑，您可以使用更一般但仍然易于处理的问题，即在每个弧上找到具有最小值和最大值的流，并将 4 编码为实验室到汇弧的下限。)