1

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

一般的有：

  1. 每个实验都必须准确分配给 R 实验室
  2. 每个实验室的最大实验次数，M
  3. 理想情况下，每个实验室的实验分布接近均匀（但可以稍微放松）
  4. 没有实验室被遗漏

然后是具体的限制。由于并非所有实验室都拥有相同的设备和试剂，因此每个实验室都会有自己的一组可以/无法执行的实验。

在我看来，这似乎是一个满足约束的问题。我知道它们存在，但我没有与它们合作的经验。

我想知道是否有一种方法可以通过将其映射到已知图问题或存在足够好的算法的其他东西来解决这个问题，或者，如果失败了，是否有优化搜索的方法，是否需要蛮力-强迫。

谢谢！

4

2 回答 2

3

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

这满足了 1 和 2 以及哪些实验室可以进行哪些实验的具体限制。我希望您可以调整M以满足约束 3 和 4，但如果没有，您可以将公式扩展为更通用的整数程序，并在实验分布方面增加额外的约束。

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

于 2019-01-25T14:44:12.970 回答
1

我建议使用建模为布尔可满足性问题/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://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)

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

于 2019-01-26T00:18:11.670 回答