1
$\begingroup$

Suppose that I have a table A with each of its n columns corresponding to an "individual" and each of its m rows corresponding to a "task". The element of the jth row and ith column, s(ji), is a real number, which can be interpreted as a score measuring the quality of match between individual i and task j.

A second table, B has n columns and two rows. The first row of column i specifies the maximum number of tasks that individual i can be assigned to. The second row specifies the minimum number of tasks that individual i can be assigned to (the two values might be equal).

A third table, C has m columns and two rows. The first row of column j specifies the maximum number of individuals that task j can be assigned to. The second row specifies the minimum number of individuals that task j can be assigned to (the two values might be equal).

The elements of B and C are natural numbers.

I would like to output an n column, m row table with element I(ji) equal to 1 if individual i is assigned to task j and zero otherwise, such that the constraints given in the second and third tables are satisfied and the output maximises the total score,

$$\sum_{i,j}I_{ij}s_{ji}.$$

As an example, suppose we have the following input:

A={{5,3},{1,2}}
B={{1,1},{1,0}}
C={{1,1},{1,1}}

Table A says, for instance, that individual 1 has a score of 5 for task 1 and 1 for task 2. Table B says that individual 1 should be assigned exactly 1 task, while individual 2 should be assigned between 0 and 1 tasks. Table C says each task should have no less than one individual and no more than one individual assigned. The solution (and desired output) is

{{1,0},{0,1}}

i.e. we assign individual 1 to task 1 and individual 2 to task 2 because that maximises the score (5+2) subject to the constraints. While we could get a higher score by, for example, giving task 1 to both individuals (total score is then 5+3), this would violate the constraint in C.

This is for practical use, so a numerical approach that finds an approximately correct solution would also be fine. If there is a more convenient way to supply the scores/constraints then that is also fine.

I have no idea how to even start programming this in Mathematica. Is anyone able to offer any direction?

$\endgroup$
  • $\begingroup$ your terminology is unclear, what do you mean by "slot"? "individual"? Maybe a small example would be useful. Slot has a specific meaning in mathematica by the way: reference.wolfram.com/language/ref/Slot.html I assume that's not what you mean. $\endgroup$ – george2079 May 9 '18 at 20:19
  • $\begingroup$ @george2079 I have added an example and switched the term slot for task. I also edited the first paragraph a little to try to be clearer that the terminology "individual" and "task" are just arbitrary lables for the two entities I want to assign to one another in the (constrained) optimal fashion. $\endgroup$ – Ubiquitous May 9 '18 at 20:44
  • $\begingroup$ related: Efficient solution for a discrete assignment problem with pairwise costs $\endgroup$ – kglr May 9 '18 at 20:51
  • $\begingroup$ see also: FindMaximumFlow $\endgroup$ – kglr May 9 '18 at 20:55
2
$\begingroup$
a = {{5, 3}, {1, 2}}
b = {{1, 1}, {1, 0}}
c = {{1, 1}, {1, 1}}

some functions to check the criteria:

c1[result_] := 
 And @@ Table[ 
   c[[i, 1]] >= Total@result[[All, i]] >= c[[i, 2]]  , {i, 
    Length@result[[1]]}]
c2[result_] := 
 And @@ Table[ 
   b[[i, 1]] >= Total@result[[i]] >= b[[i, 2]]  , {i, Length@result}]

and calculate the score:

score[result_] := Total@MapThread[ Dot, { a, result }]

check:

result={{1,0},{0,1}}
c1[result] (*True*)
c2[result] (*True*)
score[result, a] (* 7 *)

now for this small problem NMaximise gets the solution.. ( same approach as here https://mathematica.stackexchange.com/a/88226/2079 with different constraints )

create an result array:

result = Array[ v , {2, 2}]
unknowns = Flatten@result

NMaximize[{score[result], 
  c1[result] && c2[result] && 
   And @@ (0 <= # <= 1 & /@ Flatten[result])} , unknowns , Integers ]

{7., {v[1,1] -> 1, v[1,2] -> 0, v[2,1] -> 0, v[2,2] -> 1}}

result /. %[[2]]

{{1, 0}, {0, 1}}

$\endgroup$
  • $\begingroup$ Thanks, this is great! With a few tweaks it works for arbitrary m and n. $\endgroup$ – Ubiquitous May 10 '18 at 20:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.