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