[9] | 1 | /* ASSIGN, Assignment Problem */ |
---|
| 2 | |
---|
| 3 | /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ |
---|
| 4 | |
---|
| 5 | /* The assignment problem is one of the fundamental combinatorial |
---|
| 6 | optimization problems. |
---|
| 7 | |
---|
| 8 | In its most general form, the problem is as follows: |
---|
| 9 | |
---|
| 10 | There are a number of agents and a number of tasks. Any agent can be |
---|
| 11 | assigned to perform any task, incurring some cost that may vary |
---|
| 12 | depending on the agent-task assignment. It is required to perform all |
---|
| 13 | tasks by assigning exactly one agent to each task in such a way that |
---|
| 14 | the total cost of the assignment is minimized. |
---|
| 15 | |
---|
| 16 | (From Wikipedia, the free encyclopedia.) */ |
---|
| 17 | |
---|
| 18 | param m, integer, > 0; |
---|
| 19 | /* number of agents */ |
---|
| 20 | |
---|
| 21 | param n, integer, > 0; |
---|
| 22 | /* number of tasks */ |
---|
| 23 | |
---|
| 24 | set I := 1..m; |
---|
| 25 | /* set of agents */ |
---|
| 26 | |
---|
| 27 | set J := 1..n; |
---|
| 28 | /* set of tasks */ |
---|
| 29 | |
---|
| 30 | param c{i in I, j in J}, >= 0; |
---|
| 31 | /* cost of allocating task j to agent i */ |
---|
| 32 | |
---|
| 33 | var x{i in I, j in J}, >= 0; |
---|
| 34 | /* x[i,j] = 1 means task j is assigned to agent i |
---|
| 35 | note that variables x[i,j] are binary, however, there is no need to |
---|
| 36 | declare them so due to the totally unimodular constraint matrix */ |
---|
| 37 | |
---|
| 38 | s.t. phi{i in I}: sum{j in J} x[i,j] <= 1; |
---|
| 39 | /* each agent can perform at most one task */ |
---|
| 40 | |
---|
| 41 | s.t. psi{j in J}: sum{i in I} x[i,j] = 1; |
---|
| 42 | /* each task must be assigned exactly to one agent */ |
---|
| 43 | |
---|
| 44 | minimize obj: sum{i in I, j in J} c[i,j] * x[i,j]; |
---|
| 45 | /* the objective is to find a cheapest assignment */ |
---|
| 46 | |
---|
| 47 | solve; |
---|
| 48 | |
---|
| 49 | printf "\n"; |
---|
| 50 | printf "Agent Task Cost\n"; |
---|
| 51 | printf{i in I} "%5d %5d %10g\n", i, sum{j in J} j * x[i,j], |
---|
| 52 | sum{j in J} c[i,j] * x[i,j]; |
---|
| 53 | printf "----------------------\n"; |
---|
| 54 | printf " Total: %10g\n", sum{i in I, j in J} c[i,j] * x[i,j]; |
---|
| 55 | printf "\n"; |
---|
| 56 | |
---|
| 57 | data; |
---|
| 58 | |
---|
| 59 | /* These data correspond to an example from [Christofides]. */ |
---|
| 60 | |
---|
| 61 | /* Optimal solution is 76 */ |
---|
| 62 | |
---|
| 63 | param m := 8; |
---|
| 64 | |
---|
| 65 | param n := 8; |
---|
| 66 | |
---|
| 67 | param c : 1 2 3 4 5 6 7 8 := |
---|
| 68 | 1 13 21 20 12 8 26 22 11 |
---|
| 69 | 2 12 36 25 41 40 11 4 8 |
---|
| 70 | 3 35 32 13 36 26 21 13 37 |
---|
| 71 | 4 34 54 7 8 12 22 11 40 |
---|
| 72 | 5 21 6 45 18 24 34 12 48 |
---|
| 73 | 6 42 19 39 15 14 16 28 46 |
---|
| 74 | 7 16 34 38 3 34 40 22 24 |
---|
| 75 | 8 26 20 5 17 45 31 37 43 ; |
---|
| 76 | |
---|
| 77 | end; |
---|