# Assignment to slots with inequality constraints

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?

• 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. May 9 '18 at 20:19
• @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. May 9 '18 at 20:44
• – kglr
May 9 '18 at 20:51
– kglr
May 9 '18 at 20:55

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}}

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