GLPK, the GNU Linear Programming Kit, is a piece of software which solves linear optimization problems. You only have to modell the problem.
Installation
sudo apt-get install glpk-utils libglpk-dev glpk-doc python-glpk
Assignment problem
The following file is in the examples of GLPK. Save it as problem.mod:
param m, integer, > 0;
/* number of agents */
param n, integer, > 0;
/* number of tasks */
set I := 1..m;
/* set of agents */
set J := 1..n;
/* set of tasks */
param c{i in I, j in J}, >= 0;
/* cost of allocating task j to agent i */
var x{i in I, j in J}, >= 0;
/* x[i,j] = 1 means task j is assigned to agent i
note that variables x[i,j] are binary, however, there is no need to
declare them so due to the totally unimodular constraint matrix */
s.t. phi{i in I}: sum{j in J} x[i,j] <= 1;
/* each agent can perform at most one task */
s.t. psi{j in J}: sum{i in I} x[i,j] = 1;
/* each task must be assigned exactly to one agent */
minimize obj: sum{i in I, j in J} c[i,j] * x[i,j];
/* the objective is to find a cheapest assignment */
solve;
printf "\n";
printf "Agent Task Cost\n";
printf{i in I} "%5d %5d %10g\n", i, sum{j in J} j * x[i,j],
sum{j in J} c[i,j] * x[i,j];
printf "----------------------\n";
printf " Total: %10g\n", sum{i in I, j in J} c[i,j] * x[i,j];
printf "\n";
data;
/* These data correspond to an example from [Christofides]. */
/* Optimal solution is 76 */
param m := 8;
param n := 8;
param c : 1 2 3 4 5 6 7 8 :=
1 13 21 20 12 8 26 22 11
2 12 36 25 41 40 11 4 8
3 35 32 13 36 26 21 13 37
4 34 54 7 8 12 22 11 40
5 21 6 45 18 24 34 12 48
6 42 19 39 15 14 16 28 46
7 16 34 38 3 34 40 22 24
8 26 20 5 17 45 31 37 43 ;
end;
Now run it with
glpsol --model assignment.mod
You will see
GLPSOL: GLPK LP/MIP Solver, v4.57
Parameter(s) specified in the command line:
--model assignment.mod
Reading model section from assignment.mod...
Reading data section from assignment.mod...
assignment.mod:60: warning: final NL missing before end of file
60 lines were read
Generating phi...
Generating psi...
Generating obj...
Model has been successfully generated
GLPK Simplex Optimizer, v4.57
17 rows, 64 columns, 192 non-zeros
Preprocessing...
16 rows, 64 columns, 128 non-zeros
Scaling...
A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part is 16
0: obj = 2.240000000e+02 inf = 7.000e+00 (1)
13: obj = 1.750000000e+02 inf = 0.000e+00 (0)
* 28: obj = 7.600000000e+01 inf = 0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Time used: 0.0 secs
Memory used: 0.2 Mb (192291 bytes)
Agent Task Cost
1 1 13
2 8 8
3 7 13
4 5 12
5 2 6
6 6 16
7 4 3
8 3 5
----------------------
Total: 76
Model has been successfully processed