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