1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/examples/assign.mod	Mon Dec 06 13:09:21 2010 +0100
     1.3 @@ -0,0 +1,77 @@
     1.4 +/* ASSIGN, Assignment Problem */
     1.5 +
     1.6 +/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
     1.7 +
     1.8 +/* The assignment problem is one of the fundamental combinatorial
     1.9 +   optimization problems.
    1.10 +
    1.11 +   In its most general form, the problem is as follows:
    1.12 +
    1.13 +   There are a number of agents and a number of tasks. Any agent can be
    1.14 +   assigned to perform any task, incurring some cost that may vary
    1.15 +   depending on the agent-task assignment. It is required to perform all
    1.16 +   tasks by assigning exactly one agent to each task in such a way that
    1.17 +   the total cost of the assignment is minimized.
    1.18 +
    1.19 +   (From Wikipedia, the free encyclopedia.) */
    1.20 +
    1.21 +param m, integer, > 0;
    1.22 +/* number of agents */
    1.23 +
    1.24 +param n, integer, > 0;
    1.25 +/* number of tasks */
    1.26 +
    1.27 +set I := 1..m;
    1.28 +/* set of agents */
    1.29 +
    1.30 +set J := 1..n;
    1.31 +/* set of tasks */
    1.32 +
    1.33 +param c{i in I, j in J}, >= 0;
    1.34 +/* cost of allocating task j to agent i */
    1.35 +
    1.36 +var x{i in I, j in J}, >= 0;
    1.37 +/* x[i,j] = 1 means task j is assigned to agent i
    1.38 +   note that variables x[i,j] are binary, however, there is no need to
    1.39 +   declare them so due to the totally unimodular constraint matrix */
    1.40 +
    1.41 +s.t. phi{i in I}: sum{j in J} x[i,j] <= 1;
    1.42 +/* each agent can perform at most one task */
    1.43 +
    1.44 +s.t. psi{j in J}: sum{i in I} x[i,j] = 1;
    1.45 +/* each task must be assigned exactly to one agent */
    1.46 +
    1.47 +minimize obj: sum{i in I, j in J} c[i,j] * x[i,j];
    1.48 +/* the objective is to find a cheapest assignment */
    1.49 +
    1.50 +solve;
    1.51 +
    1.52 +printf "\n";
    1.53 +printf "Agent  Task       Cost\n";
    1.54 +printf{i in I} "%5d %5d %10g\n", i, sum{j in J} j * x[i,j],
    1.55 +   sum{j in J} c[i,j] * x[i,j];
    1.56 +printf "----------------------\n";
    1.57 +printf "     Total: %10g\n", sum{i in I, j in J} c[i,j] * x[i,j];
    1.58 +printf "\n";
    1.59 +
    1.60 +data;
    1.61 +
    1.62 +/* These data correspond to an example from [Christofides]. */
    1.63 +
    1.64 +/* Optimal solution is 76 */
    1.65 +
    1.66 +param m := 8;
    1.67 +
    1.68 +param n := 8;
    1.69 +
    1.70 +param c : 1  2  3  4  5  6  7  8 :=
    1.71 +      1  13 21 20 12  8 26 22 11
    1.72 +      2  12 36 25 41 40 11  4  8
    1.73 +      3  35 32 13 36 26 21 13 37
    1.74 +      4  34 54  7  8 12 22 11 40
    1.75 +      5  21  6 45 18 24 34 12 48
    1.76 +      6  42 19 39 15 14 16 28 46
    1.77 +      7  16 34 38  3 34 40 22 24
    1.78 +      8  26 20  5 17 45 31 37 43 ;
    1.79 +
    1.80 +end;