使用OR-Tools CP-SAT加速大规模分配问题求解-Python教程-PHP中文网

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

DDD

发布： 2025-11-09 12:38:18

原创

429人浏览过

使用or-tools cp-sat加速大规模分配问题求解

本文探讨了如何通过OR-Tools的CP-SAT求解器加速解决大规模分配问题，特别是当传统线性求解器（如SCIP）在处理N大于40-50个工人/任务时性能下降的问题。文章将详细介绍CP-SAT的优势、其在处理整数模型和浮点系数方面的特点，并提供一个将线性规划模型转换为CP-SAT模型的完整代码示例，以实现更高效的问题求解。

1. 问题背景与挑战

在实际应用中，将工人分配给任务是一个常见的优化问题，其目标通常是最小化总成本、最大化效率或满足一系列复杂约束。OR-Tools库提供了强大的线性规划（Linear Programming, LP）和混合整数规划（Mixed Integer Programming, MIP）求解器，如基于SCIP后端的pywraplp.Solver。然而，当问题规模（例如，工人/任务数量N）增加到一定程度（如N>40-50）时，这些通用求解器的求解时间可能会显著增加，甚至变得不切实际。

原始问题描述了一个复杂的分配场景，包括：

目标函数： 最小化所有工人中最高分配成本与最低分配成本之间的差异。
核心约束：
- 每个工人恰好分配给一个任务。
- 每个任务恰好分配给一个工人。
- 特定任务只能分配给具有特定ID的工人。
- 一组任务必须分配给具有相同ID的工人。
- 一组任务所分配工人的ID之和必须在限定范围内。

这些约束和目标函数在数学上都可以表示为整数变量和线性关系。由于问题的核心是纯整数模型（尽管成本是浮点数，但可以通过缩放转换为整数），因此选择一个专为整数规划设计的求解器至关重要。

2. CP-SAT求解器：高效处理整数模型

OR-Tools中的CP-SAT（Constraint Programming - SAT）求解器是为解决约束规划（Constraint Programming）和布尔可满足性（Satisfiability, SAT）问题而设计的高性能工具。它在处理大规模整数变量和布尔变量的组合优化问题方面表现卓越，通常比通用MIP求解器更快，尤其适用于具有复杂逻辑约束的整数模型。

AI建筑知识问答

用人工智能ChatGPT帮你解答所有建筑问题

查看详情

CP-SAT的优势：

专为整数优化设计： CP-SAT内部采用先进的搜索算法和启发式方法，能够高效地探索整数解空间。
内部浮点系数缩放： 尽管CP-SAT是整数求解器，但它能够智能地处理浮点系数。它会尝试在内部对浮点系数进行缩放，将其转换为整数，从而允许模型包含浮点数据。然而，对于关键的浮点数据（如成本），手动进行显式缩放通常能提供更好的控制和精度。
强大的约束传播： CP-SAT在添加约束时会进行积极的约束传播，快速剪枝不可行解空间，从而加速求解过程。

3. 将线性规划模型转换为CP-SAT模型

为了加速原始分配问题的求解，我们将展示如何将基于pywraplp.Solver的模型转换为使用cp_model.CpModel和cp_model.CpSolver的模型。

3.1 原始模型概述

原始模型使用pywraplp.Solver（后端为SCIP），定义了二值变量x[i, j]表示工人i是否分配给任务j。它通过辅助变量tasks_ids、max_cost和min_cost来构建复杂的约束和目标函数。

from ortools.linear_solver import pywraplp
import numpy as np

# 示例数据设置 (与原问题相同)
N = 40
np.random.seed(0)
costs = np.random.rand(N, N) * 100
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])
max_cost_limit = np.max(costs)
min_cost_limit = np.min(costs)

# Solver (原始代码使用SCIP)
# solver = pywraplp.Solver.CreateSolver("SCIP")

# # 变量定义 (原始代码)
# x = {}
# for i in range(num_workers):
#   for j in range(num_tasks):
#      x[i, j] = solver.IntVar(0, 1, "")

# tasks_ids = []
# for j in range(num_tasks):
#    tasks_ids.append( solver.Sum([workers_id[i]*x[i, j] for i in range(num_workers)]) )

# # ... 约束和目标定义 ...

登录后复制

3.2 转换为CP-SAT模型

以下是使用CP-SAT重构上述问题的完整代码。主要变化包括：

导入cp_model模块。
创建cp_model.CpModel()实例来定义模型。
创建cp_model.CpSolver()实例来求解模型。
变量类型：solver.IntVar(0, 1, "") 变为 model.NewBoolVar()。对于非布尔整数变量，使用 model.NewIntVar(lower_bound, upper_bound, name)。
约束表达：solver.Add(solver.Sum(...)) 变为 model.Add(sum(...)) 或 model.AddLinearConstraint(...)。
浮点数处理：CP-SAT主要处理整数。对于成本这类浮点数，需要手动进行缩放（例如，乘以1000或10000）以将其转换为整数，然后才能在模型中使用。
max_cost和min_cost的定义：CP-SAT提供了AddMaxEquality和AddMinEquality等专用约束来处理最大值和最小值。

from ortools.sat.python import cp_model
import numpy as np

# 示例数据设置 (与原问题相同)
N = 40
np.random.seed(0)
costs = np.random.rand(N, N) * 100
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])
max_cost_limit = np.max(costs)
min_cost_limit = np.min(costs)

# 1. 创建CP-SAT模型实例
model = cp_model.CpModel()

# 2. 变量定义
# x[i, j] 是一个布尔变量，如果工人 i 分配给任务 j，则为 1
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] 是一个整数变量，表示任务 j 分配到的工人ID
# 需要为每个任务的ID创建一个IntVar，并添加约束使其等于相应工人ID与x[i,j]的乘积之和
tasks_ids = []
# 假设工人ID的范围是 0 到 3 (A, B, C, D)
max_worker_id_value = max(idsrt_2_id_dict.values())
for j in range(num_tasks):
    task_id_var = model.NewIntVar(0, max_worker_id_value, f"task_id_{j}")
    # 约束：task_id_var == sum(workers_id[i] * x[i, j] for i in range(num_workers))
    model.Add(task_id_var == sum(workers_id[i] * x[i, j] for i in range(num_workers)))
    tasks_ids.append(task_id_var)

# 3. 约束定义

# 约束：每个工人恰好分配给一个任务。
for i in range(num_workers):
    model.Add(sum(x[i, j] for j in range(num_tasks)) == 1)

# 约束：每个任务恰好分配给一个工人。
for j in range(num_tasks):
    model.Add(sum(x[i, j] for i in range(num_workers)) == 1)

# 约束：任务 1 只能分配给 ID 为 "A" 的工人。
model.Add(tasks_ids[1] == idsrt_2_id_dict["A"])

# 约束：任务 2, 4, 6 必须分配给具有相同 ID 的工人。
model.Add(tasks_ids[2] == tasks_ids[4])
model.Add(tasks_ids[2] == tasks_ids[6])

# 约束：任务 10, 11, 12 必须分配给具有相同 ID 的工人。
model.Add(tasks_ids[10] == tasks_ids[11])
model.Add(tasks_ids[11] == tasks_ids[12])

# 约束：任务 1, 2, 3 的工人 ID 之和 <= 4。
model.Add(sum([tasks_ids[1], tasks_ids[2], tasks_ids[3]]) <= 4)

# 约束：任务 4, 5, 6 的工人 ID 之和 <= 4。
model.Add(sum

登录后复制

以上就是使用OR-Tools CP-SAT加速大规模分配问题求解的详细内容，更多请关注php中文网其它相关文章！