Google OR-Tools : 指定與分配 - 1. Solving an Assignment Problem

原文連結
範例：
有五名工人（編號為0-4）和四項任務（編號為0-3）
下表中列出了分配工作人員的成本

	任務0	任務1	任務2	任務3
0號工人	90	80	75	70
1號工人	35	85	55	65
2號工人	125	95	90	95
3號工人	45	110	95	115
4號工人	50	100	90	100

問題是要如何讓每個工人最多只能分配給一個任務，

且沒有兩個工人執行同一任務，

同時將總成本降至最低

可使用MIP或CP-SAT，我們選擇MIP來翻譯

# Step 1: Import the or linear solver, or MIP, or cp_model

from ortools.linear_solver import pywraplp

# Step 2: Add the solution printer

此步驟不用

# Step 3: Declare the linear solver, or MIP, or cp_model

solver = pywraplp.Solver('simple_mip_program',
                             pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

# Step 4: Create a database and requests

    costs = [
        [90, 80, 75, 70],
        [35, 85, 55, 65],
        [125, 95, 90, 95],
        [45, 110, 95, 115],
        [50, 100, 90, 100],
    ]
    num_workers = len(costs)
    num_tasks = len(costs[0])

將每一個工人在每一項任務所需的花費列成一個list
再把他們組成一個array

# Step 5: Create the variables

    # Variables
    # x[i, j] is an array of 0-1 variables, which will be 1
    # if worker i is assigned to task j.
    x = {}
    for i in range(num_workers):
        for j in range(num_tasks):
            x[i, j] = solver.IntVar(0, 1, '')

創造一個 x[i, j] 變數，他會是一個0或1的整數
假設被指定到這個工作，那他就是1，如果沒有的話就是0

# Step 6: Define the constraints

    for i in range(num_workers):
        solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) <= 1)

每個工人最多只能被指定一項工作：
每一個工人 i 在這麼多項任務j中最多只能有一個是1，其他都要是0
所以 x[i, j] 加總起來要小於等於1

for j in range(num_tasks):
        solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) == 1)

每個任務僅分配給一個工人：
每一項任務 j ，在這些工人 i 中只能有一個人是 1，其他都是0
所以 x[i, j] 加總起來要等於1

# Step 7: Define the objective

    objective_terms = []
    for i in range(num_workers):
        for j in range(num_tasks):
            objective_terms.append(costs[i][j] * x[i, j])
    solver.Minimize(solver.Sum(objective_terms))

讓costs[i][j] * x[i, j] 這兩者相乘
只有 x[i, j] 不為0時才有可能為正數，與cost相乘為正
目標是讓花費最低

# Step 8: Create a solver and invoke solve

status = solver.Solve()

# Step 9: Call a printer and display the results

    if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
        print('Total cost = ', solver.Objective().Value(), '\n')
        for i in range(num_workers):
            for j in range(num_tasks):
                # Test if x[i,j] is 1 (with tolerance for floating point arithmetic).
                if x[i, j].solution_value() > 0.5:
                    print('Worker %d assigned to task %d.  Cost = %d' %
                          (i, j, costs[i][j]))

最後可以得到：

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