本文旨在解决使用`ortools.linear_solver`处理大规模指派问题时遇到的性能瓶颈，特别是当问题规模（n）超过40-50时。针对包含复杂定制约束（如特定id分配、id分组及id和限制）以及最小化最高与最低成本差值的目标函数，我们推荐并详细演示如何通过迁移至or-tools的cp-sat求解器来显著提升求解速度，同时提供浮点系数处理和性能调优的实践指导。
指派问题是运筹学中的经典问题，旨在将一组工作者分配给一组任务，以优化特定目标。当问题规模较小或约束相对简单时，ortools.linear_solver（特别是结合SCIP后端）是一个强大且灵活的工具。然而，对于大规模问题（例如，N超过40-50），尤其当问题包含整数变量、复杂逻辑约束以及如最小化最高与最低成本差异等非线性目标时，linear_solver的求解时间可能会急剧增加，变得不切实际。
问题描述与原始方法分析
假设我们面临一个复杂的指派问题，其核心要求包括：
目标函数：最小化所有工作者中被分配任务的最高成本与最低成本之间的差值。工作者特性：每位工作者拥有一个特定ID（例如“A”、“B”、“C”、“D”）。定制约束：某些任务只能分配给具有特定ID的工作者。某些任务集合必须分配给具有相同ID的工作者。某些任务集合所分配工作者的ID值之和必须限制在特定范围内（例如，将“A”映射为0，“B”映射为1等）。
原始实现中，用户采用了pywraplp.Solver.CreateSolver(“SCIP”)来构建模型。SCIP是一个强大的混合整数规划（MIP）求解器，能够处理整数和连续变量。然而，对于纯整数模型或高度组合性的问题，SCIP可能不如专门的约束规划（CP）求解器高效。当问题规模增大时，SCIP在探索搜索空间时可能需要更多时间。用户提出的关于调整参数（如PRESOLVE_ON）或提供初始解的疑问，虽然在某些情况下可能有所帮助，但对于这种类型的性能瓶颈，通常需要考虑更换更适合的求解器。
推荐解决方案：使用OR-Tools CP-SAT求解器
对于上述问题，由于其本质上是一个纯整数模型（尽管成本是浮点数，但分配决策是0-1整数），并且包含大量的离散约束和组合特性，OR-Tools的CP-SAT求解器是更优的选择。CP-SAT是Google开发的一个强大的约束规划和SAT求解器，在处理整数变量、布尔变量和各种逻辑约束方面表现卓越，尤其擅长处理大规模的组合优化问题。
CP-SAT的优势在于：
专为整数和布尔变量优化：它内部使用了多种先进的启发式算法和传播技术，能够高效地剪枝搜索空间。处理复杂约束：CP-SAT原生支持各种复杂的逻辑约束，如AddMaxEquality、AddMinEquality等，这些在传统线性规划中可能需要引入大量辅助变量和MIP技巧才能表达。性能优异：在许多整数规划和约束规划基准测试中，CP-SAT都展现出领先的性能。
将模型迁移到CP-SAT
以下是将原始linear_solver模型转换为CP-SAT模型的详细步骤和示例代码。
1. 导入必要的库
from ortools.sat.python import cp_modelimport numpy as np
2. 定义问题参数和数据
与原代码相同，定义工作者、任务数量、成本矩阵和工作者ID。
# number of workers and tasksN = 40 # Increased to N=70 for demonstration of scalability# cost table for each worker-task pairsnp.random.seed(0)costs = np.random.rand(N,N)*100# workers IDs workers_id = (np.random.rand(N)*4).astype(np.uint32)id_2_idsrt_dict = {0: 'A', 1: 'B', 2: 'C', 3: 'D'} workers_id_str = [id_2_idsrt_dict[val] for val in workers_id]idsrt_2_id_dict = {idstr: id for id, idstr in id_2_idsrt_dict.items()}num_workers = len(costs)num_tasks = len(costs[0])
3. 处理浮点成本：整数化
CP-SAT主要处理整数。原始问题中的costs是浮点数。为了在CP-SAT中使用，我们需要将其转换为整数。最常见的方法是乘以一个足够大的因子（例如100或1000）并取整，从而保留足够的精度。
# Scale costs to integers to use with CP-SAT# Multiplying by 100 to keep two decimal places precisionscaling_factor = 100scaled_costs = (costs * scaling_factor).astype(int)# Determine bounds for scaled costsmin_scaled_cost_val = int(np.min(scaled_costs))max_scaled_cost_val = int(np.max(scaled_costs))# Max possible cost for a single worker (since each worker takes one task)# This is also the upper bound for max_cost and lower bound for min_costmax_possible_worker_cost = max_scaled_cost_valmin_possible_worker_cost = min_scaled_cost_val
4. 创建CP-SAT模型和变量
使用cp_model.CpModel()创建模型。
x[i, j]：布尔变量，表示工作者i是否分配给任务j。tasks_ids[j]：整数变量，表示任务j分配的工作者的ID。其取值范围是0到3（对应’A’到’D’）。
# Create the CP-SAT modelmodel = cp_model.CpModel()# Variables# x[i, j] is a 0-1 variable, which will be 1 if worker i is assigned to task j.x = {}for i in range(num_workers): for j in range(num_tasks): x[i, j] = model.NewBoolVar(f"x_{i}_{j}")# tasks_ids[j] is an integer variable containing each task's assigned worker id.# Worker IDs range from 0 to 3.tasks_ids = []for j in range(num_tasks): # The ID for a task will be the ID of the worker assigned to it. # We define its range from 0 to 3 (corresponding to 'A' to 'D'). tasks_ids.append( model.NewIntVar(0, 3, f"task_id_{j}") ) # Link task_id to the worker_id of the assigned worker # tasks_ids[j] == sum(workers_id[i] * x[i, j] for i in range(num_workers)) model.Add(tasks_ids[j] == sum(workers_id[i] * x[i, j] for i in range(num_workers)))
5. 添加约束
将原始问题中的所有约束迁移到CP-SAT模型。
# Constraint: Each worker is assigned to exactly one task.for i in range(num_workers): model.Add(sum(x[i, j] for j in range(num_tasks)) == 1)# Constraint: 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) # Constraint: Task 1 can be assigned only with workers that have the id "A" model.Add(tasks_ids[1] == idsrt_2_id_dict["A"]) # Constraint: Tasks 2,4,6 must assigned with workers of the same idmodel.Add(tasks_ids[2] == tasks_ids[4]) model.Add(tasks_ids[2] == tasks_ids[6]) # Constraint: Tasks 10,11,12 must assigned with workers of the same idmodel.Add(tasks_ids[10] == tasks_ids[11]) model.Add(tasks_ids[11] == tasks_ids[12]) # Constraint: Tasks 1,2,3 sum of ids <= 4model.Add((tasks_ids[1] + tasks_ids[2] + tasks_ids[3]) <= 4) # Constraint: Tasks 4,5,6 sum of ids <= 4model.Add((tasks_ids[4] + tasks_ids[5] + tasks_ids[6]) <= 4) # Constraint: Tasks 7,8,9 sum of ids <= 3model.Add((tasks_ids[7] + tasks_ids[8] + tasks_ids[9]) <= 3)
6. 定义目标函数：最小化成本差异
这是CP-SAT展现其优势的关键部分。为了最小化最高成本与最低成本的差值，我们需要引入辅助变量并使用AddMaxEquality和AddMinEquality。
# Objective: minimize the difference of assignment higher cost worker and lower cost worker# List of scaled costs for each worker's assignmentassignment_workers_scaled_costs_vars = []for i in range(num_workers): # Each worker's cost is the sum of scaled_costs[i][j] * x[i,j] for their assigned task. # The bounds for this variable are min_possible_worker_cost to max_possible_worker_cost. worker_cost_var = model.NewIntVar(min_possible_worker_cost, max_possible_worker_cost, f'worker_scaled_cost_{i}') model.Add(worker_cost_var == sum(scaled_costs[i][j] * x[i, j] for j in range(num_tasks))) assignment_workers_scaled_costs_vars.append(worker_cost_var)# Additional variables for max and min costsmax_cost_var = model.NewIntVar(min_possible_worker_cost, max_possible_worker_cost, 'max_scaled_cost') min_cost_var = model.NewIntVar(min_possible_worker_cost, max_possible_worker_cost, 'min_scaled_cost')# Constraints to update max and min costs using CP-SAT's dedicated functionsmodel.AddMaxEquality(max_cost_var, assignment_workers_scaled_costs_vars)model.AddMinEquality(min_cost_var, assignment_workers_scaled_costs_vars)# Minimize the difference between max and min costsmodel.Minimize(max_cost_var - min_cost_var)
7. 求解模型
创建cp_model.CpSolver()实例并调用Solve()方法。
# Create a solver and solve the model.solver = cp_model.CpSolver()# Optional: Configure solver parameters for tuning# solver.parameters.log_search_progress = True # Enable logging to see solver progress# solver.parameters.num_workers = 8 # Use multiple cores for parallel search (if applicable)# solver.parameters.max_time_in_seconds = 60.0 # Set a time limitprint(f"Solving with CP-SAT solver version: {solver.CpSolverVersion()}")status = solver.Solve(model)# Print solution.if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE: # The objective value is scaled, so divide by scaling_factor to get original units objective_diff = solver.ObjectiveValue() / scaling_factor print(f"Difference (min_max_cost) = {objective_diff:.2f}n") print(f"Max scaled cost: {solver.Value(max_cost_var) / scaling_factor:.2f}") print(f"Min scaled cost: {solver.Value(min_cost_var) / scaling_factor:.2f}") for i in range(num_workers): for j in range(num_tasks): if solver.Value(x[i, j]) > 0.5: # If x[i,j] is 1 print(f"Worker {i} ({workers_id_str[i]}) assigned to task {j}." + f" Original Cost: {costs[i][j]:.2f}, Scaled Cost: {scaled_costs[i][j]}")else: print("No solution found.") if status == cp_model.INFEASIBLE: print("The problem is infeasible.") elif status == cp_model.MODEL_INVALID: print("The model is invalid.") else: print(f"Solver status: {solver.StatusName(status)}")
CP-SAT性能调优与注意事项
浮点数处理：如上所示，对于CP-SAT，最佳实践是将所有浮点系数（如成本）手动缩放为整数。虽然CP-SAT内部会尝试自动缩放，但手动缩放可以提供更好的控制和可预测性。缩放因子应根据所需精度和数值范围来选择，避免溢出。参数设置：CP-SAT提供了丰富的参数来调优求解过程。可以通过solver.parameters对象进行设置。`solver.parameters
以上就是使用OR-Tools CP-SAT加速大规模指派问题求解的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1380516.html
微信扫一扫 
支付宝扫一扫 
