Google OR-Tools : 指定與分配 - 4. Assignment with Allowed Groups - MIP solver
| 任務0 | 任務1 | 任務2 | 任務3 | 任務4 | 任務5 | |
| 0號工人 | 90 | 76 | 75 | 70 | 50 | 74 |
| 1號工人 | 35 | 85 | 55 | 65 | 48 | 101 |
| 2號工人 | 125 | 95 | 90 | 105 | 59 | 120 |
| 3號工人 | 45 | 110 | 95 | 115 | 104 | 83 |
| 4號工人 | 60 | 105 | 80 | 75 | 59 | 62 |
| 5號工人 | 45 | 65 | 110 | 95 | 47 | 31 |
| 6號工人 | 38 | 51 | 107 | 41 | 69 | 99 |
| 7號工人 | 47 | 85 | 57 | 71 | 92 | 77 |
| 8號工人 | 39 | 63 | 97 | 49 | 118 | 56 |
| 9號工人 | 47 | 101 | 71 | 60 | 88 | 109 |
| 10號工人 | 17 | 39 | 103 | 64 | 61 | 92 |
| 11號工人 | 101 | 45 | 83 | 59 | 92 | 27 |
這次的分配問題，有以下條件
1) 將工人分成3組，每組取2人來分配任務
2) 每個任務只能分配給一個工人
3) 每個工人只能做一件任務
4) 花費最少
在該範例中，有12個工人，編號為0-11。
每4個工人分成一個group(1~3)
每個group裡任意2人組成一對
再從三個group裡各選一對
再從三個group裡各選一對
（ex, [2,3], [4,7], [8,10] -> [2,3,4,7,8,10] ）
所以最後總共有5*5*5種可能
group1 = [[2, 3], # Subgroups of workers 0 - 3
[1, 3],
[1, 2],
[0, 1],
[0, 2]]
group2 = [[6, 7], # Subgroups of workers 4 - 7
[5, 7],
[5, 6],
[4, 5],
[4, 7]]
group3 = [[10, 11], # Subgroups of workers 8 - 11
[9, 11],
[9, 10],
[8, 10],
[8, 11]]
這次選用CP-SAT來解
# Step 1: Import the linear solver, or MIP, or cp_model
from __future__ import print_function
from ortools.sat.python import cp_model
import time
import numpy as np
# Step 2: Add the solution printer
此步驟不需# Step 3: Declare the linear solver, or MIP, or cp_model
model = cp_model.CpModel()
start = time.time()
# Step 4: Create a database and requests
cost = [[90, 76, 75, 70, 50, 74],
[35, 85, 55, 65, 48, 101],
[125, 95, 90, 105, 59, 120],
[45, 110, 95, 115, 104, 83],
[60, 105, 80, 75, 59, 62],
[45, 65, 110, 95, 47, 31],
[38, 51, 107, 41, 69, 99],
[47, 85, 57, 71, 92, 77],
[39, 63, 97, 49, 118, 56],
[47, 101, 71, 60, 88, 109],
[17, 39, 103, 64, 61, 92],
[101, 45, 83, 59, 92, 27]]
num_workers = len(cost)
num_tasks = len(cost[1])
group1 = [[0, 0, 1, 1], # Workers 2, 3
[0, 1, 0, 1], # Workers 1, 3
[0, 1, 1, 0], # Workers 1, 2
[1, 1, 0, 0], # Workers 0, 1
[1, 0, 1, 0]] # Workers 0, 2
group2 = [[0, 0, 1, 1], # Workers 6, 7
[0, 1, 0, 1], # Workers 5, 7
[0, 1, 1, 0], # Workers 5, 6
[1, 1, 0, 0], # Workers 4, 5
[1, 0, 0, 1]] # Workers 4, 7
group3 = [[0, 0, 1, 1], # Workers 10, 11
[0, 1, 0, 1], # Workers 9, 11
[0, 1, 1, 0], # Workers 9, 10
[1, 0, 1, 0], # Workers 8, 10
[1, 0, 0, 1]] # Workers 8, 11
ex. 在group1的第一個list中 [0,0,1,1] 表示選擇worker2,3工作
被選中工作的為1，沒被選到的為0
# Step 5-1: Create the variables
x = []
for i in range(num_workers):
t = []
for j in range(num_tasks):
t.append(model.NewIntVar(0, 1, "x[%i,%i]" % (i, j)))
x.append(t)
x_array = [x[i][j] for i in range(num_workers) for j in range(num_tasks)]
設一個list為x，裡面包含12個(num_workers) list t
讓每個工人針對每一項任務形成一個0 or 1 的變數(x[i, j])
0表示沒工作，1表示有工作
ex. 每個list t如下
[x[0,0](0..1), x[0,1](0..1), x[0,2](0..1), x[0,3](0..1), x[0,4](0..1), x[0,5](0..1), x[0,6](0..1), x[0,7](0..1)],
[x[1,0](0..1), x[1,1](0..1), x[1,2](0..1), x[1,3](0..1), x[1,4](0..1), x[1,5](0..1)]...
# Step 6-2: Define the constraints
# Each task is assigned to at least one worker.
[model.Add(sum(x[i][j] for i in range(num_workers)) == 1)
for j in range(num_tasks)]
也可以寫成下列：
# Each task is assigned to exactly one worker.
for j in range(num_tasks):
model.Add(sum(x[i][j] for i in range(num_workers)) == 1)
x[0,0],x[1,0],x[2,0],x[3,0],x[4,0]只能有一個為１，其他都是０
x[0,1],x[1,1],x[2,1],x[3,1],x[4,1]只能有一個為１，其他都是０
之後都類似
# Each worker is assigned to at most one task.
[model.Add(sum(x[i][j] for j in range(num_tasks)) <= 1)
for i in range(num_workers)]
x[0,0],x[0,1],x[0,2],x[0,3]最多只能有一個為１，其他都是０
x[1,0],x[1,1],x[1,2],x[1,3]最多只能有一個為１，其他都是０
之後都類似
# Step 5-2: Create the variables
這邊要創造另外一個變數 list work 用來顯示每個工人是否有做哪項任務
# Create variables for each worker, indicating whether they work on some task.
work = []
for i in range(num_workers):
work.append(model.NewIntVar(0, 1, "work[%i]" % i))
變量work [i]是0-1變量，指示工作狀態或每個工人。
也就是說，如果將工作者i分配給任務，則work [i]等於1，否則為0。
# Step 6-2: Define the constraints
for i in range(num_workers):
for j in range(num_tasks):
model.Add(work[i] == sum(x[i][j] for j in range(num_tasks)))
並且讓work[i]等於x[i][j] （兩者同時為0 or 1）
PS.
work[i]用於讓之後的結果會在指定的group中
x[i][j]用於讓之後的結果會符合前面的約束
# Define the allowed groups of worders
model.AddAllowedAssignments([work[0], work[1], work[2], work[3]], group1)
model.AddAllowedAssignments([work[4], work[5], work[6], work[7]], group2)
model.AddAllowedAssignments([work[8], work[9], work[10], work[11]], group3)
AddAllowedAssignments(variables, tuples_list)是對"變量數組(array of variable)"的約束，它要求在分配答案時，"結果數組(resulting array)"會是tuple_list中的其中一個list
（ex. 表示work [0-3]這四個變數的工作狀態必須符合group 1的其中一組如[0,1,1,0]表示，不可以變成像[0,1,1,1]，一定要在group中選出剛好只有兩位工人工作）
# Step 7: Define the objective
model.Minimize(sum([np.dot(x_row, cost_row) for (x_row, cost_row) in zip(x, cost)]))
將x, cost兩條一維list相乘
dot()在一維數組時，是把兩條list的每一個元素與另外一條list的元素相乘之後，再把相乘得到的數全部相加）
# Step 8: Create a solver and invoke solve
solver = cp_model.CpSolver()
status = solver.Solve(model)
# Step 9: Call a printer and display the results
if status == cp_model.OPTIMAL:
print('Minimum cost = %i' % solver.ObjectiveValue())
print()
for i in range(num_workers):
for j in range(num_tasks):
if solver.Value(x[i][j]) == 1:
print('Worker ', i, ' assigned to task ', j, ' Cost = ', cost[i][j])
print()
end = time.time()
print("Time = ", round(end - start, 4), "seconds")
可得到下面結果：
Minimum cost = 239 Worker 0 assigned to task 4 Cost = 50 Worker 1 assigned to task 2 Cost = 55 Worker 5 assigned to task 5 Cost = 31 Worker 6 assigned to task 3 Cost = 41 Worker 10 assigned to task 0 Cost = 17 Worker 11 assigned to task 1 Cost = 45 Time = 0.0113 seconds
留言
張貼留言