Assignment Problem solved with Python / OR-Tools

Assignment Problem¶

http://en.wikipedia.org/wiki/Assignment_problem

Assignment Problems can be solved with numpy, and many other python libraries.

One of the simplest ways to solve an Assignment Problem is with Python and Google OR-Tools:

http://developers.google.com/optimization/assignment/simple_assignment

Here is a walk-through of the small example problem at the OR-Tools page. A much larger problem is solved afterward.¶

(OR-Tools needs to be installed with pip; see the Installation tab)

In [1]:

from ortools.graph import pywrapgraph

In [2]:

def create_data_array():
    cost = [[90, 76, 75, 70],
            [35, 85, 55, 65],
            [125, 95, 90, 105],
            [45, 110, 95, 115]]
    return cost

In [3]:

cost = create_data_array()
rows = len(cost)
cols = len(cost[0])

In [4]:

assignment = pywrapgraph.LinearSumAssignment()
for worker in range(rows):
    for task in range(cols):
        if cost[worker][task]:
            assignment.AddArcWithCost(worker, task, cost[worker][task])

In [5]:

%%time
solve_status = assignment.Solve()

CPU times: user 39 µs, sys: 4 µs, total: 43 µs
Wall time: 47.7 µs

In [6]:

if solve_status == assignment.OPTIMAL:
    print('Total cost = ', assignment.OptimalCost())
    print()
    for i in range(0, assignment.NumNodes()):
        print('Worker %d assigned to task %d.  Cost = %d' % (
            i,
            assignment.RightMate(i),
            assignment.AssignmentCost(i)))
elif solve_status == assignment.INFEASIBLE:
    print('No assignment is possible.')
elif solve_status == assignment.POSSIBLE_OVERFLOW:
    print('Some input costs are too large and may cause an integer overflow.')    

Total cost =  265

Worker 0 assigned to task 3.  Cost = 70
Worker 1 assigned to task 2.  Cost = 55
Worker 2 assigned to task 1.  Cost = 95
Worker 3 assigned to task 0.  Cost = 45

---

The key Solve step runs very quickly. This is not surprising since there are only 4! different assignments to be scored.

---

Let's try a much larger problem!¶

What happens if N=100? Below, A random 100x100 cost matrix is created in the function create_data_array2.

In [7]:

import random
def create_data_array2():
    randomcost = []
    for i in range(0,100):
        randomrow = []
        for j in range(0,100):
            n = random.randint(0,10000)
            randomrow.append(n)
        randomcost.append(randomrow)
    return randomcost

In [8]:

cost = create_data_array2()
rows = len(cost)
cols = len(cost[0])

In [9]:

assignment = pywrapgraph.LinearSumAssignment()
for worker in range(rows):
    for task in range(cols):
        if cost[worker][task]:
            assignment.AddArcWithCost(worker, task, cost[worker][task])

In [10]:

%%time
solve_status = assignment.Solve()

CPU times: user 1.09 ms, sys: 118 µs, total: 1.21 ms
Wall time: 1.23 ms

In [11]:

if solve_status == assignment.OPTIMAL:
    print('Total cost = ', assignment.OptimalCost())
    print()
    for i in range(0, assignment.NumNodes()):
        print('Worker %d assigned to task %d.  Cost = %d' % (
            i,
            assignment.RightMate(i),
            assignment.AssignmentCost(i)))
elif solve_status == assignment.INFEASIBLE:
    print('No assignment is possible.')
elif solve_status == assignment.POSSIBLE_OVERFLOW:
    print('Some input costs are too large and may cause an integer overflow.')   

Total cost =  15092

Worker 0 assigned to task 64.  Cost = 225
Worker 1 assigned to task 71.  Cost = 458
Worker 2 assigned to task 53.  Cost = 215
Worker 3 assigned to task 52.  Cost = 32
Worker 4 assigned to task 38.  Cost = 352
Worker 5 assigned to task 79.  Cost = 389
Worker 6 assigned to task 42.  Cost = 253
Worker 7 assigned to task 58.  Cost = 176
Worker 8 assigned to task 87.  Cost = 308
Worker 9 assigned to task 77.  Cost = 76
Worker 10 assigned to task 50.  Cost = 352
Worker 11 assigned to task 59.  Cost = 118
Worker 12 assigned to task 68.  Cost = 39
Worker 13 assigned to task 2.  Cost = 147
Worker 14 assigned to task 62.  Cost = 14
Worker 15 assigned to task 91.  Cost = 137
Worker 16 assigned to task 89.  Cost = 19
Worker 17 assigned to task 49.  Cost = 77
Worker 18 assigned to task 16.  Cost = 294
Worker 19 assigned to task 57.  Cost = 314
Worker 20 assigned to task 86.  Cost = 186
Worker 21 assigned to task 36.  Cost = 3
Worker 22 assigned to task 96.  Cost = 99
Worker 23 assigned to task 7.  Cost = 46
Worker 24 assigned to task 10.  Cost = 181
Worker 25 assigned to task 43.  Cost = 96
Worker 26 assigned to task 94.  Cost = 58
Worker 27 assigned to task 29.  Cost = 238
Worker 28 assigned to task 6.  Cost = 62
Worker 29 assigned to task 81.  Cost = 47
Worker 30 assigned to task 30.  Cost = 149
Worker 31 assigned to task 51.  Cost = 92
Worker 32 assigned to task 5.  Cost = 57
Worker 33 assigned to task 13.  Cost = 170
Worker 34 assigned to task 39.  Cost = 37
Worker 35 assigned to task 32.  Cost = 330
Worker 36 assigned to task 54.  Cost = 448
Worker 37 assigned to task 3.  Cost = 77
Worker 38 assigned to task 19.  Cost = 14
Worker 39 assigned to task 27.  Cost = 149
Worker 40 assigned to task 92.  Cost = 397
Worker 41 assigned to task 17.  Cost = 204
Worker 42 assigned to task 24.  Cost = 295
Worker 43 assigned to task 67.  Cost = 48
Worker 44 assigned to task 25.  Cost = 330
Worker 45 assigned to task 61.  Cost = 24
Worker 46 assigned to task 74.  Cost = 133
Worker 47 assigned to task 48.  Cost = 78
Worker 48 assigned to task 41.  Cost = 244
Worker 49 assigned to task 55.  Cost = 123
Worker 50 assigned to task 31.  Cost = 12
Worker 51 assigned to task 14.  Cost = 19
Worker 52 assigned to task 37.  Cost = 443
Worker 53 assigned to task 45.  Cost = 199
Worker 54 assigned to task 70.  Cost = 52
Worker 55 assigned to task 44.  Cost = 36
Worker 56 assigned to task 76.  Cost = 151
Worker 57 assigned to task 97.  Cost = 54
Worker 58 assigned to task 72.  Cost = 25
Worker 59 assigned to task 65.  Cost = 93
Worker 60 assigned to task 4.  Cost = 109
Worker 61 assigned to task 34.  Cost = 59
Worker 62 assigned to task 88.  Cost = 22
Worker 63 assigned to task 78.  Cost = 142
Worker 64 assigned to task 80.  Cost = 47
Worker 65 assigned to task 60.  Cost = 149
Worker 66 assigned to task 69.  Cost = 216
Worker 67 assigned to task 11.  Cost = 343
Worker 68 assigned to task 15.  Cost = 270
Worker 69 assigned to task 47.  Cost = 57
Worker 70 assigned to task 40.  Cost = 32
Worker 71 assigned to task 12.  Cost = 112
Worker 72 assigned to task 75.  Cost = 180
Worker 73 assigned to task 23.  Cost = 368
Worker 74 assigned to task 8.  Cost = 84
Worker 75 assigned to task 63.  Cost = 138
Worker 76 assigned to task 35.  Cost = 60
Worker 77 assigned to task 1.  Cost = 128
Worker 78 assigned to task 26.  Cost = 60
Worker 79 assigned to task 20.  Cost = 382
Worker 80 assigned to task 33.  Cost = 35
Worker 81 assigned to task 21.  Cost = 49
Worker 82 assigned to task 98.  Cost = 360
Worker 83 assigned to task 95.  Cost = 89
Worker 84 assigned to task 46.  Cost = 380
Worker 85 assigned to task 9.  Cost = 49
Worker 86 assigned to task 56.  Cost = 15
Worker 87 assigned to task 82.  Cost = 291
Worker 88 assigned to task 99.  Cost = 65
Worker 89 assigned to task 22.  Cost = 140
Worker 90 assigned to task 0.  Cost = 78
Worker 91 assigned to task 85.  Cost = 353
Worker 92 assigned to task 28.  Cost = 14
Worker 93 assigned to task 84.  Cost = 5
Worker 94 assigned to task 90.  Cost = 84
Worker 95 assigned to task 66.  Cost = 153
Worker 96 assigned to task 83.  Cost = 7
Worker 97 assigned to task 73.  Cost = 43
Worker 98 assigned to task 93.  Cost = 191
Worker 99 assigned to task 18.  Cost = 239

The solve time is still only a fraction of a second on a slow laptop computer. Clearly, the OR-Tools can easily solve very large problems of this type.¶