ortools系列：分配問題建模成整數規劃問題
ortools系列：分配問題建模成整數規劃問題
混合整數規劃問題
起那麼我們講瞭如何使用最小成本流來解決分配問題。這裡我們講如何使用更通用的混合整數規劃(MIP)求解器來解決相同的問題。對於這個特定的問題，最小成本流比MIP要快。另一方面，MIP可以解決比最小成本流更大的一類問題。
將分配問題作為MIP問題來解決，其基本思想是將整型變數分配到問題圖形的邊緣。每個變數的值是流經相應邊緣的流。對於給定worker和任務之間的邊，如果將worker分配給任務，則變數的值為1，否則為0。
from ortools.linear_solver import pywraplp
def main():
# 初始化混合整數規劃求解器
solver = pywraplp.Solver(SolveAssignmentProblemMIP,
pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
# 成本矩陣是最小成本流圖對應的成本數
cost = [[90, 76, 75, 70],
[35, 85, 55, 65],
[125, 95, 90, 105],
[45, 110, 95, 115],
[60, 105, 80, 75],
[45, 65, 110, 95]]
#
team1 = [0, 2, 4]
team2 = [1, 3, 5]
team_max = 2
num_workers = len(cost)
num_tasks = len(cost[1])
x = {}
# 創建0-1布爾變數，和我們之前的不一樣，我之前是創建整數變數
# 創建0-1布爾變數，可以減少搜索空間，搜索效率更高效
for i in range(num_workers):
for j in range(num_tasks):
x[i, j] = solver.BoolVar(x[%i,%i] % (i, j))
# Objective
# 目標函數，其實就是 cost * x 的簡單方程式
solver.Minimize(solver.Sum([cost[i][j] * x[i, j] for i in range(num_workers)
for j in range(num_tasks)]))
# Constraints
# Each worker is assigned to at most 1 task.
# 添加約束，每個工人只能分配最多一個任務
for i in range(num_workers):
solver.Add(solver.Sum([x[i, j] for j in range(num_tasks)]) <= 1)
# Each task is assigned to exactly one worker.
# 添加約束，每個任務必須被分配出去，並且只有一個工人認領該任務
for j in range(num_tasks):
solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) == 1)
# Each team takes on two tasks.
# 添加約束，每個團隊任務不能超過2個
solver.Add(solver.Sum([x[i, j] for i in team1 for j in range(num_tasks)]) <= team_max)
solver.Add(solver.Sum([x[i, j] for i in team2 for j in range(num_tasks)]) <= team_max)
# 最後就是調用求解器求解了
sol = solver.Solve()
print(Total 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 %d assigned to task %d. Cost = %d % (
i,
j,
cost[i][j]))
print()
print("Time = ", solver.WallTime(), " milliseconds")
if __name__ == __main__:
main()
# 結果
Total cost = 250.0
Worker 0 assigned to task 2. Cost = 75
Worker 1 assigned to task 0. Cost = 35
Worker 4 assigned to task 3. Cost = 75
Worker 5 assigned to task 1. Cost = 65
Time = 293 milliseconds
建模成MIP問題似乎邏輯更加清晰一些，你覺得呢。
3. 參考
- google_ortools_guide
大家看完記得關注點贊.
master蘇.
推薦閱讀：