Allocating M experiments to N labs while respecting constraints

Question

I have the following problem: I have to allocate K experiments to N labs, while respecting some general constraints and some specific ones.

The general ones are:

1. each experiment has to be allocated to exactly R labs
2. there's a maximum number of experiments per lab, M
3. ideally the distribution of experiments per lab is close to uniform (but that can be somewhat relaxed)
4. no lab is left out

Then there's the specific constraints. Since not all labs have the same equipment and reagents, each lab will have their own set of experiments that they can/can't perform.

This seems to me to be a problem of satisfying constraints. I know they exist, but I have no experience working with them.

I was wondering if there is a way of solving this by mapping it to a know graph problem or something else for which a good enough algorithm exists, or, failing that, if there's a method to optimize the search, if it needs to be brute-forced.

Thanks!

Answer 1

I'd recommend solving this as a constraint satisfaction problem using modeled as a boolean satisfiability problem/SAT.

To do so, define K*N boolean variables for each combination of experiment and lab. If a variable is true it indicates that a given experiment is to be performed at a given lab.

The constraints you supply can then be modeled using these variables. For instance, if the variables are named x(experiment,lab) and we have three labs and wish to perform Experiment 1 at two of them, this implies the constraint:

( 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) )

All of your other constraints can be written similarly. However, this exponential explosion of clauses is distressing. Fortunately, good modeling tools can automatically insert additional variables to make such cardinality constraints much more efficient.

Below, I've developed a full implementation for solving your problem using the Z3 solver:

#!/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)

The solution generated by the above is chosen "randomly" from all the many possible solutions to the problem. If you're not happy with the solution you can rule it out by ANDing together all the outputs provided by the solution, negating, and adding this as a new constraint.