Which driver should take which round?
The assignment problem asks how to match each worker to exactly one job so that the total cost is as small as possible. A delivery firm with three drivers and three rounds meets it every morning.
The cheapest match is not always the one that looks cheapest driver by driver, and you will see why.
By the end of this lesson
Note
I can solve a small assignment problem.
Key words
| Word | What it means |
|---|---|
| Assignment problem | matching each worker to one job at the lowest total cost |
| Cost table | a grid with the cost of each worker on each job |
| Brute force | trying every possible answer and keeping the best |
| Greedy choice | taking the cheapest option now without looking ahead |
| Transport problem | sending goods from depots to shops at the lowest cost |
The cells students fill in are left blank in this preview.
One driver for each round
Three drivers, A, B and C, share three delivery rounds. Each driver has a cost in minutes for each round, which depends on where they live and the vans they drive.
The rule is one driver for each round and one round for each driver. The aim is the smallest total of minutes.
Worked example: the cost table in minutes
| Driver | Round 1 | Round 2 | Round 3 |
|---|---|---|---|
| A | 9 | 2 | 7 |
| B | 6 | 4 | 3 |
| C | 5 | 8 | 1 |
The cells students fill in are left blank in this preview.
With three drivers there are only six matches
Driver A has 3 choices, driver B then has 2 and driver C is left with 1. That makes 3 x 2 x 1 = 6 matches. For a small problem you can simply list them all.
This is brute force: try every answer and keep the cheapest.
Let Python try all six
docker exec jupyter python3 -c "from itertools import permutations; C = [[9, 2, 7], [6, 4, 3], [5, 8, 1]]; print(min(sum(C[i][p[i]] for i in range(3)) for p in permutations(range(3))))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Worked example: all six matches and their totals
| A takes | B takes | C takes | Total minutes |
|---|---|---|---|
| Round 1 | Round 2 | Round 3 | 14 |
| Round 1 | Round 3 | Round 2 | 20 |
| Round 2 | Round 1 | Round 3 | 9 |
| Round 2 | Round 3 | Round 1 | 10 |
| Round 3 | Round 1 | Round 2 | 21 |
| Round 3 | Round 2 | Round 1 | 16 |
The cells students fill in are left blank in this preview.
A greedy choice can miss the cheapest match
A quick idea is to let each driver take their cheapest round in turn. A takes round 2 for 2 minutes. B takes round 3 for 3. C is left with round 1 for 5. The total is 10.
The cheapest match costs 9. The greedy choice for B used up round 3, which C needed.
A common mistake
Warning
Many people think that choosing the cheapest option at each step gives the cheapest total. It does not, because an early choice removes options later. Compare whole matches, not single steps.
A solver avoids trying every match
With 20 drivers there are more matches than anyone could list. The assignment problem has a fast method, and SciPy has it as linear_sum_assignment.
It returns two arrays: the rows and the column chosen for each row. Counting from 0, the rows are drivers A, B and C.
Ask SciPy for the cheapest match
docker exec jupyter python3 -c "from scipy.optimize import linear_sum_assignment as lsa; print(lsa([[9, 2, 7], [6, 4, 3], [5, 8, 1]]))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Reading the two arrays
The command printed rows 0 1 2 and columns 1 0 2. Driver A (row 0) takes column 1, which is round 2. Driver B takes round 1 and driver C round 3.
This is the same match as the one that totalled 9 minutes by brute force.
A transport problem ships goods from depots
A transport problem is a cousin of the assignment problem. Depots hold stock, shops need stock, and each route has a cost for every box. The aim is the cheapest way to meet every need.
It is a linear program with equalities: every depot sends all of its stock and every shop receives what it needs.
Worked example: two depots and two shops
| Route | Cost a box in pence | Stock or need |
|---|---|---|
| Depot 1 to shop 1 | 4 | Depot 1 holds 30 |
| Depot 1 to shop 2 | 6 | Depot 2 holds 20 |
| Depot 2 to shop 1 | 5 | Shop 1 needs 25 |
| Depot 2 to shop 2 | 3 | Shop 2 needs 25 |
The cells students fill in are left blank in this preview.
Solve the transport problem
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([4, 6, 5, 3], A_eq=[[1, 1, 0, 0], [0, 0, 1, 1], [1, 0, 1, 0], [0, 1, 0, 1]], b_eq=[30, 20, 25, 25]); print(r.fun, r.x)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Going further
Change one number in the cost table so that the greedy match and the cheapest match are the same. Say which number you changed and why it works.
Then count the matches for six drivers and say whether you would still list them by hand.