J.C. Kantor (Kantor.1@nd.edu)
This IPython notebook demonstrates models for various types of assignment problems using GLPK/MathProg.
from IPython.core.display import HTML
HTML(open("styles/custom.css", "r").read())
You work as a logistics manager for a toy manufacturer, and you currently have five delivery trucks on the road. Your trucks are in Austin, Boston, Chicago, Denver, Edmonton, and Fargo. You need them to drive to five other cities: Atlanta, Boise, Charlotte, Dallas, and Fresno. The table below shows the distance in miles between these cities.
From\To | Atlanta | Boise | Charlotte | Dallas | Fresno |
---|---|---|---|---|---|
Austin | 921 | 1627 | 1166 | 196 | 1594 |
Boston | 1078 | 2661 | 837 | 1767 | 3107 |
Chicago | 716 | 1693 | 756 | 925 | 2140 |
Denver | 1400 | 815 | 1561 | 788 | 1142 |
Edmonton | 3764 | 1718 | 3848 | 3310 | 2835 |
Where should you send each of your trucks in order to minimize travel distance?
How many ways are there to assign destinations to each truck?
$N = 5 \times 4 \times 3 \times 2 \times 1 = 120$
In general there are
$N = n!$
ways to assign $n$ resources to $n$ tasks.
n = arange(0,10)
plot(n,n);
xlabel('Number of Resources/Tasks');
xlabel('Number of Resources/Tasks')
plot(n,n,n,n**2)
legend(['n','n**2'],loc='best');
<matplotlib.legend.Legend at 0x107f6ec50>
xlabel('Number of Resources/Tasks')
plot(n,n,n,n**2,n,exp(n))
legend(['n','n**2','exp(n)'],loc='best');
<matplotlib.legend.Legend at 0x107fb03d0>
xlabel('Number of Resources/Tasks')
semilogy(n,n,n,n**2,n,exp(n),n,map(math.factorial,n))
legend(['n','n**2','exp(n)','n!'],loc='best');
<matplotlib.legend.Legend at 0x107fd29d0>
Assignment problems can be incredibly difficult to solve. The speed of solution will depend on the exact details of the problem, what features can be left out without affecting the utility of the solution, and the availability of specialized algorithms.
Let x[R,T] be a binary variable where x[R,T] = 1 means resource R is assigned to task T.
One resource must be assigned to each task. So for all $t\in TASKS$
$$\sum_{r \in RESOURCES} x[R,T] = 1$$Each resource must be assigned to one task. So for all $r\in RESOURCES$
$$\sum_{t \in TASKS} x[R,T] = 1$$%%writefile Assign.mod
set RESOURCES;
set TASKS;
param a {RESOURCES,TASKS} >= 0;
var x {RESOURCES,TASKS} binary;
minimize Cost: sum{r in RESOURCES, t in TASKS} a[r,t]*x[r,t];
subject to R {r in RESOURCES}: sum {t in TASKS} x[r,t] = 1;
subject to T {t in TASKS}: sum {r in RESOURCES} x[r,t] = 1;
solve;
printf "\n\n";
for {r in RESOURCES} {
for {t in TASKS : x[r,t] == 1} {
printf "Assign %10s to %10s Cost: %6.0f\n", r, t, a[r,t];
}
}
printf "\n\n";
end;
Overwriting Assign.mod
%%script glpsol -m Assign.mod -d /dev/stdin
set RESOURCES := Austin Boston Chicago Denver Edmonton ;
set TASKS := Atlanta Boise Charlotte Dallas Fresno ;
param a : Atlanta Boise Charlotte Dallas Fresno :=
Austin 921 1627 1166 196 1594
Boston 1078 2661 837 1767 3107
Chicago 716 1693 756 925 2140
Denver 1400 815 1561 788 1142
Edmonton 3764 1718 3848 3310 2835 ;
end;
GLPSOL: GLPK LP/MIP Solver, v4.52 Parameter(s) specified in the command line: -m Assign.mod -d /dev/stdin Reading model section from Assign.mod... Assign.mod:23: warning: final NL missing before end of file 23 lines were read Reading data section from /dev/stdin... /dev/stdin:12: warning: final NL missing before end of file 12 lines were read Generating Cost... Generating R... Generating T... Model has been successfully generated GLPK Integer Optimizer, v4.52 11 rows, 25 columns, 75 non-zeros 25 integer variables, all of which are binary Preprocessing... 10 rows, 25 columns, 50 non-zeros 25 integer variables, all of which are binary 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 9 Solving LP relaxation... GLPK Simplex Optimizer, v4.52 10 rows, 25 columns, 50 non-zeros 0: obj = 1.211800000e+04 infeas = 3.000e+00 (1) * 7: obj = 8.790000000e+03 infeas = 0.000e+00 (1) * 17: obj = 4.609000000e+03 infeas = 0.000e+00 (1) OPTIMAL LP SOLUTION FOUND Integer optimization begins... + 17: mip = not found yet >= -inf (1; 0) + 17: >>>>> 4.609000000e+03 >= 4.609000000e+03 0.0% (1; 0) + 17: mip = 4.609000000e+03 >= tree is empty 0.0% (0; 1) INTEGER OPTIMAL SOLUTION FOUND Time used: 0.0 secs Memory used: 0.1 Mb (150106 bytes) Assign Austin to Dallas Cost: 196 Assign Boston to Charlotte Cost: 837 Assign Chicago to Atlanta Cost: 716 Assign Denver to Fresno Cost: 1142 Assign Edmonton to Boise Cost: 1718 Model has been successfully processed
A foreman has five workers and five jobs to complete. The time in hours each worker needs to complete each job is shown in the following table.
Resource\Task | Job 1 | Job 2 | Job 3 | Job 4 | Job 5 |
---|---|---|---|---|---|
Worker 1 | 3 | 4 | 8 | 7 | 8 |
Worker 2 | 2 | 5 | 3 | 2 | 6 |
Worker 3 | 7 | 9 | 1 | 8 | 3 |
Worker 4 | 5 | 3 | 4 | 6 | 6 |
Worker 5 | 8 | 9 | 7 | 5 | 8 |
%%script glpsol -m Assign.mod -d /dev/stdin
set RESOURCES := Worker_1 Worker_2 Worker_3 Worker_4 Worker_5 ;
set TASKS := Job_1 Job_2 Job_3 Job_4 Job_5 ;
param a : Job_1 Job_2 Job_3 Job_4 Job_5 :=
Worker_1 3 4 8 7 8
Worker_2 2 5 3 2 6
Worker_3 7 9 1 8 3
Worker_4 5 3 4 6 6
Worker_5 8 9 7 5 8 ;
end;
GLPSOL: GLPK LP/MIP Solver, v4.52 Parameter(s) specified in the command line: -m Assign.mod -d /dev/stdin Reading model section from Assign.mod... Assign.mod:23: warning: final NL missing before end of file 23 lines were read Reading data section from /dev/stdin... /dev/stdin:12: warning: final NL missing before end of file 12 lines were read Generating Cost... Generating R... Generating T... Model has been successfully generated GLPK Integer Optimizer, v4.52 11 rows, 25 columns, 75 non-zeros 25 integer variables, all of which are binary Preprocessing... 10 rows, 25 columns, 50 non-zeros 25 integer variables, all of which are binary 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 9 Solving LP relaxation... GLPK Simplex Optimizer, v4.52 10 rows, 25 columns, 50 non-zeros 0: obj = 2.800000000e+01 infeas = 3.000e+00 (1) * 7: obj = 2.000000000e+01 infeas = 0.000e+00 (1) * 11: obj = 1.700000000e+01 infeas = 0.000e+00 (1) OPTIMAL LP SOLUTION FOUND Integer optimization begins... + 11: mip = not found yet >= -inf (1; 0) + 11: >>>>> 1.700000000e+01 >= 1.700000000e+01 0.0% (1; 0) + 11: mip = 1.700000000e+01 >= tree is empty 0.0% (0; 1) INTEGER OPTIMAL SOLUTION FOUND Time used: 0.0 secs Memory used: 0.1 Mb (150106 bytes) Assign Worker_1 to Job_1 Cost: 3 Assign Worker_2 to Job_4 Cost: 2 Assign Worker_3 to Job_3 Cost: 1 Assign Worker_4 to Job_2 Cost: 3 Assign Worker_5 to Job_5 Cost: 8 Model has been successfully processed
%%script glpsol -m /dev/stdin
set RESOURCES;
set TASKS;
param a {RESOURCES,TASKS} >= 0;
var x {RESOURCES,TASKS} binary;
maximize Cost: sum{r in RESOURCES, t in TASKS} a[r,t]*x[r,t];
#subject to R {r in RESOURCES}: sum {t in TASKS} x[r,t] = 1;
subject to T {t in TASKS}: sum {r in RESOURCES} x[r,t] = 1;
solve;
printf "\n\n";
for {r in RESOURCES} {
for {t in TASKS : x[r,t] == 1} {
printf "Assign %10s to %10s Cost: %6.0f\n", r, t, a[r,t];
}
}
printf "\n\n";
data;
set RESOURCES := Worker_1 Worker_2 Worker_3 Worker_4 Worker_5 ;
set TASKS := Job_1 Job_2 Job_3 Job_4 Job_5 ;
param a : Job_1 Job_2 Job_3 Job_4 Job_5 :=
Worker_1 3 4 8 7 8
Worker_2 2 5 3 2 6
Worker_3 7 9 1 8 3
Worker_4 5 3 4 6 6
Worker_5 8 9 7 5 8 ;
end;
GLPSOL: GLPK LP/MIP Solver, v4.52 Parameter(s) specified in the command line: -m /dev/stdin Reading model section from /dev/stdin... Reading data section from /dev/stdin... /dev/stdin:35: warning: final NL missing before end of file 35 lines were read Generating Cost... Generating T... Model has been successfully generated GLPK Integer Optimizer, v4.52 6 rows, 25 columns, 50 non-zeros 25 integer variables, all of which are binary Preprocessing... 5 rows, 25 columns, 25 non-zeros 25 integer variables, all of which are binary 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 5 Solving LP relaxation... GLPK Simplex Optimizer, v4.52 5 rows, 25 columns, 25 non-zeros * 0: obj = 3.700000000e+01 infeas = 0.000e+00 (0) * 3: obj = 4.100000000e+01 infeas = 0.000e+00 (0) OPTIMAL LP SOLUTION FOUND Integer optimization begins... + 3: mip = not found yet <= +inf (1; 0) + 3: >>>>> 4.100000000e+01 <= 4.100000000e+01 0.0% (1; 0) + 3: mip = 4.100000000e+01 <= tree is empty 0.0% (0; 1) INTEGER OPTIMAL SOLUTION FOUND Time used: 0.0 secs Memory used: 0.1 Mb (139304 bytes) Assign Worker_1 to Job_3 Cost: 8 Assign Worker_3 to Job_4 Cost: 8 Assign Worker_5 to Job_1 Cost: 8 Assign Worker_5 to Job_2 Cost: 9 Assign Worker_5 to Job_5 Cost: 8 Model has been successfully processed
Suppose we want to assign just two workers. What is the minimum time solution using just two workers?
%%script glpsol -m /dev/stdin
set ITEMS;
param value{ITEMS};
param cost{ITEMS};
var x {ITEMS} binary;
maximize Obj: sum{i in ITEMS} value[i]*x[i];
subject to C: sum{i in ITEMS} cost[i]*x[i] <= 12 ;
solve;
for {i in ITEMS}{
printf "%3s %2d\n",i,x[i];
}
data;
param : ITEMS : value cost :=
A 7 3
B 9 4
C 5 2
D 12 6
E 14 7
F 6 3
G 12 5 ;
end;
GLPSOL: GLPK LP/MIP Solver, v4.52 Parameter(s) specified in the command line: -m /dev/stdin Reading model section from /dev/stdin... Reading data section from /dev/stdin... /dev/stdin:29: warning: final NL missing before end of file 29 lines were read Generating Obj... Generating C... Model has been successfully generated GLPK Integer Optimizer, v4.52 2 rows, 7 columns, 14 non-zeros 7 integer variables, all of which are binary Preprocessing... 1 row, 7 columns, 7 non-zeros 7 integer variables, all of which are binary Scaling... A: min|aij| = 2.000e+00 max|aij| = 7.000e+00 ratio = 3.500e+00 Problem data seem to be well scaled Constructing initial basis... Size of triangular part is 1 Solving LP relaxation... GLPK Simplex Optimizer, v4.52 1 row, 7 columns, 7 non-zeros * 0: obj = 0.000000000e+00 infeas = 0.000e+00 (0) * 7: obj = 2.850000000e+01 infeas = 0.000e+00 (0) OPTIMAL LP SOLUTION FOUND Integer optimization begins... + 7: mip = not found yet <= +inf (1; 0) Solution found by heuristic: 26 + 9: >>>>> 2.800000000e+01 <= 2.800000000e+01 0.0% (4; 0) + 9: mip = 2.800000000e+01 <= tree is empty 0.0% (0; 7) INTEGER OPTIMAL SOLUTION FOUND Time used: 0.0 secs Memory used: 0.1 Mb (137038 bytes) A 1 B 1 C 0 D 0 E 0 F 0 G 1 Model has been successfully processed
Investment | Location | Cost (millions) | Expected Profit |
---|---|---|---|
1 | Europe | 10 | 1.0 |
2 | Europe | 8 | 0.9 |
3 | Europe | 8 | 0.9 |
4 | South America | 16 | 2.0 |
5 | South America | 12 | 1.4 |
6 | Africa | 4 | 0.2 |
7 | Africa | 6 | 0.5 |
8 | Africa | 16 | 2.1 |
The objective is to maximize the total expected profits subject to: