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