The latest version of this IPython notebook is available at http://github.com/jckantor/ESTM60203 for noncommercial use under terms of the Creative Commons Attribution Noncommericial ShareAlike License (CC BY-NC-SA 4.0).

J.C. Kantor ([email protected])

Assignment Problems

This IPython notebook demonstrates models for various types of assignment problems using GLPK/MathProg.

Initializations

In [1]:
from IPython.core.display import HTML
HTML(open("styles/custom.css", "r").read())
Out[1]:

Example Problem

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?

Combinatorial Complexity

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.

In [26]:
n = arange(0,10)
plot(n,n);
xlabel('Number of Resources/Tasks');
In [28]:
xlabel('Number of Resources/Tasks')
plot(n,n,n,n**2)
legend(['n','n**2'],loc='best');
Out[28]:
<matplotlib.legend.Legend at 0x107f6ec50>
In [29]:
xlabel('Number of Resources/Tasks')
plot(n,n,n,n**2,n,exp(n))
legend(['n','n**2','exp(n)'],loc='best');
Out[29]:
<matplotlib.legend.Legend at 0x107fb03d0>
In [31]:
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');
Out[31]:
<matplotlib.legend.Legend at 0x107fd29d0>

Types of Complexity

$$ Combinatoric >> Exponential >> Geometric >> Linear $$

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.

Formulation

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$$

In [9]:
%%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

Solution

In [10]:
%%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

Example

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

What is the minimum time solution if one worker is assigned to each job?

In [22]:
%%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

What is the minimum time solution if workers can be assigned multiple times?

In [23]:
%%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

Exercise

Suppose we want to assign just two workers. What is the minimum time solution using just two workers?

Knapsack Problems

Typical Applications

  • Resource allocations with financial constraints
  • Construction and scoring of a heterogenous test
  • Selection of Capital Investments

Example

Need to complete a set of jobs

A B C D E F G
Value 7 9 5 12 14 6 12
Time 3 4 2 6 7 3 5
In [24]:
%%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

Exercise

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:

  • Contractual commitments require at least 2 investments in Europe
  • There must be one South American Investment
  • No more than one African investment
  • Total cost must be less than $40 million
In [ ]: