algorithm - 在遵守约束的同时将M个实验分配给N个实验室

我有以下问题：我必须把K个实验分配给N个实验室，同时遵守一些一般的约束和一些特定的约束。
一般情况是：
每个实验都必须分配到R实验室
每个实验室有最大数量的实验，M
理想情况下，每个实验室的实验分布接近均匀（但可以稍微放宽）
没有实验室被排除在外
然后是具体的限制由于并非所有实验室都有相同的设备和试剂，因此每个实验室都有自己的一套实验，它们不能执行。
在我看来，这是一个满足约束的问题我知道他们存在，但是我没有和他们一起工作的经历。
我想知道是否有办法把它映射到一个已知的图形问题或其他一些足够好的算法存在，或者，如果它有一个方法来优化搜索，如果它需要蛮力强制的话。
谢谢！

最佳答案

我建议将其作为constraint satisfaction problem来解决，使用建模为boolean satisfiability problem/SAT。
为此，请为实验和实验室的每个组合定义k*n布尔变量。如果某个变量为真，则表示将在给定的实验室执行给定的实验。
然后，可以使用这些变量对您提供的约束进行建模。例如，如果变量名为x（实验，实验室），并且我们有三个实验室，并且希望在其中两个实验室执行实验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://stackoverflow.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: https://stackoverflow.com/questions/43081929/k-out-of-n-constraint-in-z3py
#(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)

由上述问题产生的解决方案是从所有可能的问题解决方案中“随机”选择的。如果您对解决方案不满意，可以通过将解决方案提供的所有输出放在一起、求反并将其添加为新约束来排除此问题。

关于algorithm - 在遵守约束的同时将M个实验分配给N个实验室，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54367216/