Google OR-Tools : 指定與分配 - 3. Assignment with Task Sizes - MIP solver

原文連結
如同上一篇的問題，只是這次將每個任務加入任務大小

	任務0	任務1	任務2	任務3	任務4	任務5	任務6	任務7
0號工人	90	76	75	70	50	74	12	68
1號工人	35	85	55	65	48	101	70	83
2號工人	125	95	90	105	59	120	36	73
3號工人	45	110	95	115	104	83	37	71
4號工人	60	105	80	75	59	62	93	88
5號工人	45	65	110	95	47	31	81	34
6號工人	38	51	107	41	69	99	115	45
7號工人	47	85	57	71	92	77	109	36
8號工人	39	63	97	49	118	56	92	61
9號工人	47	101	71	60	88	109	52	90

	任務0	任務1	任務2	任務3	任務4	任務5	任務6	任務7
任務大小	10	7	3	12	15	4	11	5

每個工作人員能執行的任務大小之有最大限制 15
一個人可以接受超過一項任務，
但任務大小加起來不能超過15。

這個例子裡有CP-SAT和MIP解法
我們選擇MIP解法來說明

# Step 1: Import the 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('SolveAssignmentProblemMIP',
                           pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

# Step 4: Create a database and requests

  cost = [[90, 76, 75, 70, 50, 74, 12, 68],
          [35, 85, 55, 65, 48, 101, 70, 83],
          [125, 95, 90, 105, 59, 120, 36, 73],
          [45, 110, 95, 115, 104, 83, 37, 71],
          [60, 105, 80, 75, 59, 62, 93, 88],
          [45, 65, 110, 95, 47, 31, 81, 34],
          [38, 51, 107, 41, 69, 99, 115, 48],
          [47, 85, 57, 71, 92, 77, 109, 36],
          [39, 63, 97, 49, 118, 56, 92, 61],
          [47, 101, 71, 60, 88, 109, 52, 90]]
  num_workers = len(cost)
  num_tasks = len(cost[0])
  task_sizes = [10, 7, 3, 12, 15, 4, 11, 5]
  total_size_max = 15

# Step 5: Create the variables

  x = {}

  for i in range(num_workers):
    for j in range(num_tasks):
      x[i, j] = solver.IntVar(0, 1, 'x[%i,%i]' % (i, j))

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

# Step 6: Define the constraints

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

每個工人最多只能被指定一項工作：
每一個工人 i 在這麼在各項任務j中的task size加起來要小於

total_size_max
所以 task_sizes[j] * x[i, j] 加總起來要小於等於15

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

每個任務僅至少要分配給一個工人：
每一項任務 j ，若有分配到人的是 1，沒被分配到的是0
x[i, j] 加總起來要大於等於1

# Step 7: Define the objective

solver.Minimize(solver.Sum([cost[i][j] * x[i,j] for i in range(num_workers)
                                                  for j in range(num_tasks)]))

讓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

  print('Minimum cost = ', solver.Objective().Value())
  print()
  for i in range(num_workers):
    for j in range(num_tasks):
      if x[i, j].solution_value() > 0:
        print('Worker', i,' assigned to task', j, '  Cost = ', cost[i][j])

最後可得到下圖

Minimum cost =  326.0

Worker 0  assigned to task 6   Cost =  12
Worker 1  assigned to task 0   Cost =  35
Worker 1  assigned to task 2   Cost =  55
Worker 4  assigned to task 4   Cost =  59
Worker 5  assigned to task 5   Cost =  31
Worker 5  assigned to task 7   Cost =  34
Worker 6  assigned to task 1   Cost =  51
Worker 8  assigned to task 3   Cost =  49