lundi 26 juillet 2021

Random assignment problem with constraints

Suppose I have C clusters and Q elements to be randomly distributed into the C clusters. We have to comply with the following restrictions:

  • Each cluster has capacity, i.e a number representing the number of elements that can be allocated there
  • Each cluster c_k has associated two positive numbers a_k and b_k, with k = 1, 2, ..., C. And each element q_j has associated a w_j positive number with j = 1, 2, ..., Q. The element q_j can be allocated in c_k if and only if a_k <= w_j <= b_k, for every k, j.
  • Solutions may not be found, so we have to raise an exception

For example suppose Q = 4 and C = 2, with W = [1,2,1,2] representing the w_j values, andZ = [2, 2]are the clusters capacity (each cluster can allocate 2 elements) and WT = [(0,2), (0,2)] is the vector of restrictions on the clusters. In this case any 2-permutation of the 4 elements is a valid solution.

I am here to search for references of a similar problem.




Aucun commentaire:

Enregistrer un commentaire