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苏.
推荐阅读：