lemon-project-template-glpk

comparison deps/glpk/examples/assign.mod @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:2d4c00bca2e3
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;