ortools系列：分配問題中的分組作業
ortools系列：分配問題中的分組作業
1. 分組作業
下面描述一個分配問題，在這個問題中，只允許某些工人組分配任務，在這個例子中有12個工人，編號為0 - 11，允許的組是下列工人對的組合。
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]]
允許的組可以是三對工作者的任意組合，每對工作者來自group1、group2和group3。例如，將[2,3]，[6,7]和[10,11]組合在允許的組[2,3,6,7,10,11]中。因為這三個集合都包含5個元素，所以允許的組總數是5 * 5 * 5 = 125。
請注意，如果一組worker屬於任何一個允許的組，那麼它可以是問題的解。換句話說，可行集由滿足任意一個約束條件的點組成。這是一個非凸問題的例子。相比之下，前面描述的MIP示例是一個凸問題：要使一個點可行，必須滿足所有約束。
對於像這樣的非凸問題，CP-SAT求解器通常比MIP求解器快。下面將介紹使用CP-SAT和MIP的方法，並比較這兩種解決方案的解決時間。
2. CP-SAT
# CP-SAT
from ortools.sat.python import cp_model
import time
import numpy as np
def main():
model = cp_model.CpModel()
start = time.time()
# 各個工人做對應任務的成本矩陣
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])
# 要為 CP-SAT 定義允許的工人組，需要創建二進位數組，以指示哪些工人屬於一個組。
# 例如，對於group1 (workers 0 - 3)，二進位向量[0,0,1,1]指定包含workers 2和3的組。
# 這種指定組的方式與在MIP解決方案中指定組的方式略有不同，但實際上是一樣的。
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
# Declare 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)]
# 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 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)]
# 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))
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)))
# Define the allowed groups of worders
# 對於CP-SAT，沒有必要在一個循環中創建所有這些向量的125個組合。
# CP-SAT解決程序提供了一個方法AllowedAssignments，它能夠為三組工作者(0 - 3,4 - 7和8-11)中的每一組分別指定允許的組的約束。
# 變數work[i]是0-1個變數，表示工作狀態或每個worker。也就是說，如果工人i被分配到一個任務，work[i]等於0，否則為0。
# 定義工人0-3的工作狀態必須與group1中的一個模式匹配的約束。
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)
# 創建目標
model.Minimize(sum([np.dot(x_row, cost_row) for (x_row, cost_row) in zip(x, cost)]))
# 求解問題
solver = cp_model.CpSolver()
status = solver.Solve(model)
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")
if __name__ == __main__:
main()
# 結果
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.2188 seconds
理解了描述的問題，代碼就很簡單了，接下來我們看MIP方法。
3. MIP
MIP解法生成數據的代碼是一樣的，唯一不同就是約束條件和目標函數寫法不同。
from ortools.linear_solver import pywraplp
import time
def main():
start = time.time()
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_tasks = len(cost[1])
# Allowed groups of workers:
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]]
allowed_groups = []
for i in range(len(group1)):
for j in range(len(group2)):
for k in range(len(group3)):
allowed_groups.append(group1[i] + group2[j] + group3[k])
min_val = 1e6
total_time = 0
for i in range(len(allowed_groups)):
group = allowed_groups[i]
res = assignment(cost, group)
solver_tmp = res[0]
x_tmp = res[1]
total_time = total_time + solver_tmp.WallTime()
if solver_tmp.Objective().Value() < min_val:
min_val = solver_tmp.Objective().Value()
min_index = i
min_solver = solver_tmp
min_x = x_tmp
min_group = group
print(Minimum cost = , min_val)
print()
for i in min_group:
for j in range(num_tasks):
if min_x[i, j].solution_value() > 0:
print(Worker, i, assigned to task, j, Cost = , cost[i][j])
print()
end = time.time()
print("Time = ", round(end - start, 4), "seconds")
def assignment(cost, group):
# Solve assignment problem for given group of workers.
num_tasks = len(cost[1])
# Clear values in x
solver = None
# Instantiate a mixed-integer solver
solver = pywraplp.Solver(AssignmentProblemGroups,
pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
x = None
x = {}
for i in group:
for j in range(num_tasks):
x[i, j] = solver.IntVar(0, 1, x[%i,%i] % (i, j))
# Each worker is assigned to exactly one task.
for i in group:
solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) <= 1)
# Each task is assigned to at least one worker.
for j in range(num_tasks):
solver.Add(solver.Sum([x[i, j] for i in group]) >= 1)
# Objective
solver.Minimize(solver.Sum([cost[i][j] * x[i, j] for i in group
for j in range(num_tasks)]))
solver.Solve()
res = [solver, x]
return res
if __name__ == __main__:
main()
# 結果
Minimum cost = 239.0
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.6276 seconds
4. 參考
- google_ortools_guide
大家看完記得關注點贊.
master蘇.
推薦閱讀：
