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

Question

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

一般的有：

每个实验必须恰好分配给 R 个实验室
每个实验室的实验数量上限为 M
理想情况下，每个实验室的实验分布接近均匀（但可以稍微放宽）
没有实验室被遗漏

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

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

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

谢谢！

Answer 1

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

这满足了 1 和 2 以及哪些实验室可以进行哪些实验的具体限制。我希望您可以调整 M 以满足约束 3 和 4，但如果不能，您可以将公式扩展为更一般的整数程序，对实验的分布有额外的约束。

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

Answer 2

我建议将其作为 constraint satisfaction problem using modeled as a boolean satisfiability problem/SAT 来解决。

为此，为实验和实验室的每个组合定义 K*N 布尔变量。如果一个变量为真，则表示将在给定的实验室进行给定的实验。

然后可以使用这些变量对您提供的约束进行建模。例如，如果变量命名为 x(experiment,lab) 并且我们有三个实验室并希望在其中两个实验室执行实验 1，这意味着约束：

( x(1,1) & x(1,2) & !x(1,3) ) | ( x(1,1) & !x(1,2) & x(1,3) ) | ( !x(1,1) & x(1,2) & x(1,3) )

你所有的其他约束都可以类似地写。然而，这种呈指数级增长的条款令人痛心。幸运的是，好的建模工具可以自动插入额外的变量，使这种基数约束更加有效。

下面，我开发了一个完整的实现来使用 Z3 求解器解决您的问题：

#!/usr/bin/env python3
#Richard Barnes (https://whosebug.com/users/752843/richard)
#May need to run `pip3 install z3-solver`

import functools
import itertools
import sys
import z3

class ExpLab:
  def __init__(self, num_experiments, num_labs):
    """Create binary indicator variables for each lab-experiment combination"""
    self.num_labs        = num_labs        #Number of labs
    self.num_experiments = num_experiments #Number of experiments

    #Create variables
    self.bvars = []
    for e in range(num_experiments):
      for l in range(num_labs):
        self.bvars += [ {"exp":e, "lab":l, "yn": z3.Bool("Run Experiment {0} at Lab {1}".format(e,l))} ]

  def getExpLab(self, exp, lab):
    """Get the variable indicating whether a particular experiment should be
    performed at a particular lab"""
    return [x['yn'] for x in self.bvars if x['exp']==exp and x['lab']==lab][0]

  def getExp(self, exp):
    """For a given experiment, get the indicator variables for all the labs the
    experiment might be performed at"""
    return [x['yn'] for x in self.bvars if x['exp']==exp]

  def getLab(self, lab):
    """For a given lab, get the variables associated for all of the experiments
    that might be performed at the lab"""
    return [x['yn'] for x in self.bvars if x['lab']==lab]    

  def numExperiments(self):
    return self.num_experiments

  def numLabs(self):
    return self.num_labs

#Create the binary indicator variables
el = ExpLab(num_experiments=6, num_labs=4)

s = z3.Solver()

R = 3 #Number of labs at which the experiment must be performed
M = 6 #Maximum number of experiments per lab

#See: 
#(1) each experiment has to be allocated to exactly 3 labs, 
for e in range(el.numExperiments()):
  s.add( z3.PbEq([(x,1) for x in el.getExp(e)], R) )

for l in range(el.numLabs()):
  #(2) there's a maximum number of experiments per lab (around 6)

  #NOTE: To make distributions more even, decreae the maximum number of
  #experiments a lab can perform. This isn't a perfect way of creating a smooth
  #distribution, but it will push solutions in that direction.
  experiments_at_this_lab = el.getLab(l)
  s.add( z3.PbLe([(x,1) for x in experiments_at_this_lab], M) )
  #(3) no lab is left out. 
  s.add( z3.PbGe([(x,1) for x in experiments_at_this_lab], 1) )

#Example of a specific constraint
#Don't run Experiment 3 at Lab 2
s.add( z3.Not(el.getExpLab(3,2)) )

#Check to see if the model 
if s.check()!=z3.sat:
  print("The problem has no solution!")
  sys.exit(-1)

#A solution to the problem exists... get it. Note: the solution generated is
#arbitrarily chosen from the set of all possible solutions.
m = s.model()
print(m)

上述生成的解决方案是从问题的所有可能解决方案中选择 "randomly" 的。如果您对解决方案不满意，可以通过对解决方案提供的所有输出进行 AND 运算、否定并将其添加为新约束来排除它。

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

Allocating M experiments to N labs while respecting constraints

algorithm

graph-algorithm

smt

constraint-satisfaction