Assignment to slots with inequality constraints

Question

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?

Answer 1

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