使用OR-Tools CP-SAT加速大规模指派问题求解_石家庄创泽智能科技有限公司

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

使用OR-Tools CP-SAT加速大规模指派问题求解

2025-11-16

浏览次数：次

返回列表

使用OR-Tools CP-SAT加速大规模指派问题求解

本文旨在解决使用`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_model
import numpy as np

2. 定义问题参数和数据

与原代码相同，定义工作者、任务数量、成本矩阵和工作者ID。

Zyro AI Background Remover

Zyro推出的AI图片背景移除工具

145 查看详情 Zyro AI Background Remover

# number of workers and tasks
N = 40 # Increased to N=70 for demonstration of scalability

# cost table for each worker-task pairs
np.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 precision
scaling_factor = 100
scaled_costs = (costs * scaling_factor).astype(int)

# Determine bounds for scaled costs
min_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_cost
max_possible_worker_cost = max_scaled_cost_val
min_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 model
model = 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 h*e 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 id
model.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 id
model.Add(tasks_ids[10] == tasks_ids[11]) 
model.Add(tasks_ids[11] == tasks_ids[12]) 

# Constraint: Tasks 1,2,3 sum of ids <= 4
model.Add((tasks_ids[1] + tasks_ids[2] + tasks_ids[3]) <= 4) 

# Constraint: Tasks 4,5,6 sum of ids <= 4
model.Add((tasks_ids[4] + tasks_ids[5] + tasks_ids[6]) <= 4) 

# Constraint: Tasks 7,8,9 sum of ids <= 3
model.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 assignment
assignment_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 costs
max_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 functions
model.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 costs
model.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 limit

print(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加速大规模指派问题求解的详细内容，更多请关注其它相关文章！

# 转换为 # 新干盐化工业城网站建设 # 祺越网站建设 # 南通网站建设方案托管 # seo 360 业务 # 建设图纸网站设计规范 # 三水网站推广作用 # 泰安营销小程序推广公司 # 付费seo外推快照 # 广州营销网站建设推广 # 品牌型网站建设专业定制 # 将其 # 线性规划 # 这是 # 如何做 # python # 浮点数 # 布尔 # 浮点 # 是一个 # elif # cos # 性能瓶颈 # google # win # ai # 后端 # 工具 # app # go

相关栏目：【科技资讯46185 】【网络学院92790 】

上一篇：Python中高效合并嵌套字典的策略

下一篇：YII权限控制怎么实现_YII框架RBAC权限管理配置教程

首页

关于我们

产品展示

咨询研究

新闻中心

留言板

联系我们

新闻中心 NEWS CENTER

使用OR-Tools CP-SAT加速大规模指派问题求解

问题描述与原始方法分析

推荐解决方案：使用OR-Tools CP-SAT求解器

将模型迁移到CP-SAT

1. 导入必要的库

2. 定义问题参数和数据

3. 处理浮点成本：整数化

4. 创建CP-SAT模型和变量

5. 添加约束

6. 定义目标函数：最小化成本差异

7. 求解模型

CP-SAT性能调优与注意事项