I am writing to ask if any of you know what is the name in the research literature of a particular constrained optimization problem I am facing. I would like to find a general name so that I can research better on the matter.
The problem in question is:
I have P persons that need to be assigned to T tasks (P>>T). Each person can be assigned to only one task. A particular person p_i has a different score (ability) to complete a task t_i. To simplify, let's assume the score distribution for each person p_i is a probability distribution over the tasks (sum to 1). Moreover, each task t_i has a precise capacity C_t_i which is the number of persons that must be assigned to the task. Pay attention that sum of C_t_i over i equals P so that all people can be assigned to one task. I want to find a feasible solution that maximizes the score.
- P persons
- T tasks
- p_i must be assigned to only one task
- t_i has a capacity C_t_i of people which must be assigned to t_i
- sum_over_i (C_t_i) = P
This can be visualized in a matrix S (score matrix). Find in the table below an example of score matrix S:
----------------------------
| \ T | t_1 | t_2 | t_3 |
| P \ | | | |
----------------------------
| p_1 | 0.1 | 0.2 | 0.7 | -> sum to 1
| p_2 | 0.9 | 0.1 | 0 | -> sum to 1
| p_3 | 0.1 | 0.1 | 0.8 |
| p_4 | 0.3 | 0.4 | 0.3 |
| p_5 | 0.2 | 0.2 | 0.6 |
----------------------------
| C | 1 | 2 | 2 |
----------------------------
A feasible solution to the example is the following matrix, let's call it X:
----------------------------
| \ T | t_1 | t_2 | t_3 |
| P \ | | | |
----------------------------
| p_1 | 1 | 0 | 0 |
| p_2 | 0 | 1 | 0 |
| p_3 | 0 | 0 | 1 |
| p_4 | 0 | 1 | 0 |
| p_5 | 0 | 0 | 1 |
----------------------------
| C | 1 | 2 | 2 |
----------------------------
Which has a overall score of 0.1+0.1+0.8+0.4+0.6=2. There is of course a better solution with a higher score.
The problem can be re-written in mathematical formulas such as:
find matrix X
maximizing sum_over_i_j ( X.S ) for every i in rows and j in columns
such that sum_over_j (X_i) = 1 for every i in rows and j in columns
and sum_over_i (X_j) = C_t_j for every i in rows and j in columns
Where . is the point-wise multiplication between matrices.
Thank you guys
This is called the transportation problem. The people are the supply nodes, with a supply of $1$ unit each. The tasks are the demand nodes, with demand C_t_i. The usual formulation has a minimization objective, but you can negative the objective function for maximization.