COIN-OR::LEMON - Graph Library

source: glpk-cmake/examples/assign.mod @ 2:4c8956a7bdf4

Last change on this file since 2:4c8956a7bdf4 was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 13 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 2.0 KB
Line 
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
18param m, integer, > 0;
19/* number of agents */
20
21param n, integer, > 0;
22/* number of tasks */
23
24set I := 1..m;
25/* set of agents */
26
27set J := 1..n;
28/* set of tasks */
29
30param c{i in I, j in J}, >= 0;
31/* cost of allocating task j to agent i */
32
33var 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
38s.t. phi{i in I}: sum{j in J} x[i,j] <= 1;
39/* each agent can perform at most one task */
40
41s.t. psi{j in J}: sum{i in I} x[i,j] = 1;
42/* each task must be assigned exactly to one agent */
43
44minimize obj: sum{i in I, j in J} c[i,j] * x[i,j];
45/* the objective is to find a cheapest assignment */
46
47solve;
48
49printf "\n";
50printf "Agent  Task       Cost\n";
51printf{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];
53printf "----------------------\n";
54printf "     Total: %10g\n", sum{i in I, j in J} c[i,j] * x[i,j];
55printf "\n";
56
57data;
58
59/* These data correspond to an example from [Christofides]. */
60
61/* Optimal solution is 76 */
62
63param m := 8;
64
65param n := 8;
66
67param 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
77end;
Note: See TracBrowser for help on using the repository browser.