CP-SAT Primer快速入门教程：从pip install ortools到10分钟求解100件物品背包问题（附完整代码与详解）

CP-SAT Primer快速入门教程：从pip install ortools到10分钟求解100件物品背包问题（附完整代码与详解）

【免费下载链接】cpsat-primerThe CP-SAT Primer: Using and Understanding Google OR-Tools' CP-SAT Solver项目地址: https://gitcode.com/gh_mirrors/cp/cpsat-primer

CP-SAT Primer（cpsat-primer）是一本开源的实战教程书，带你从零掌握 Google OR-Tools 中强大的 CP-SAT 约束规划求解器。本文作为快速入门指南，跟着教程走完pip install ortools一键安装、编写第一个 CP-SAT 模型，再用不到 10 分钟亲手求解一个 100 件物品的背包问题——10 亿亿种组合，0.01 秒找到可证明的全局最优解 📦。无论你是优化新手还是 MIP 老手，这篇文章都能让你快速上手。

什么是CP-SAT？为什么值得花10分钟学会它

CP-SAT 是 Google OR-Tools 套件中相对较新的求解器，融合了约束规划（CP）与 SAT 求解器的长处，能处理大量逻辑约束，在组合优化领域已经能与 Gurobi、CPLEX 等商业 MIP 求解器正面竞争，且完全开源免费。

它为什么快？因为 CP-SAT 不会枚举所有解：它通过传播、推理和剪枝，把 $2^{100} \approx 10^{30}$ 量级的搜索空间"聪明地"砍掉。一台普通笔记本（4 核以上、16GB 内存）就能驾驭绝大多数入门问题，完全不需要 GPU 或超级计算机。

第一步：pip install ortools 一键安装CP-SAT

安装极其简单，只需一行命令（Python 3 环境）：

pip3 install -U ortools

• -U会同时升级已有版本。OR-Tools 处于活跃开发中，作者建议经常更新，早期版本的一些高级功能 bug 已在后续版本修复。
• CP-SAT 是 OR-Tools 的组成部分，装完ortools即自动可用，无需额外配置。
• 作者推荐用 Jupyter Notebook 做实验，本教程的示例代码也直接来自 Notebook 风格的工作流。

完整安装与硬件建议见项目章节chapters/installation.md。

第二步：你的第一个CP-SAT优化模型（5行搞定）

CP-SAT 的编程风格是声明式的：像写 SQL 一样，只描述"要什么"（变量、约束、目标），而不是"怎么算"。先看一个能看懂数学式的最小模型：

from ortools.sat.python import cp_model model = cp_model.CpModel() # 变量：0 <= x, y <= 100 的整数 x = model.new_int_var(0, 100, "x") y = model.new_int_var(0, 100, "y") # 约束：x + y <= 30 model.add(x + y <= 30) # 目标：最大化 30x + 50y model.maximize(30 * x + 50 * y) solver = cp_model.CpSolver() solver.solve(model) print(f"{solver.status_name()}") # OPTIMAL print(f"x={solver.value(x)}, y={solver.value(y)}") # x=0, y=30

💡 注意x、y此刻并不是数字，而是占位符（IntVar对象），真正的赋值发生在求解阶段。Python 的运算符重载让30 * x + 50 * y几乎和数学写法一模一样，方便对照公式找 bug。

求解器会返回 5 种状态之一：UNKNOWN、MODEL_INVALID、FEASIBLE、INFEASIBLE、OPTIMAL。入门阶段你只需记住：看到OPTIMAL就说明找到了可证明的最优解。

这个最小例子的完整版与状态码详解在chapters/example.md。

第三步：10分钟求解100件物品背包问题（完整代码）

现在上硬菜。背包问题是 NP-hard 经典：从 100 件物品中挑选子集，使总价值最大且总重量不超过 2000。100 件物品意味着约 $2^{100}$ 种组合——即使超算每秒 $10^{18}$ 次运算，枚举也要 31000 多年。

100 件物品背包问题的完整输入数据与最优选择结果（价值 1161）

下面是可直接运行的完整代码（数据来自cpsat-primer官方示例）：

from ortools.sat.python import cp_model # pip install -U ortools # 1. 输入数据：100 件物品的重量与价值，背包容量 2000 weights = [395, 658, 113, 185, 336, 494, 294, 295, 256, 530, 311, 321, 602, 855, 209, 647, 520, 387, 743, 26, 54, 420, 667, 971, 171, 354, 962, 454, 589, 131, 342, 449, 648, 14, 201, 150, 602, 831, 941, 747, 444, 982, 732, 350, 683, 279, 667, 400, 441, 786, 309, 887, 189, 119, 209, 532, 461, 420, 14, 788, 691, 510, 961, 528, 538, 476, 49, 404, 761, 435, 729, 245, 204, 401, 347, 674, 75, 40, 882, 520, 692, 104, 512, 97, 713, 779, 224, 357, 193, 431, 442, 816, 920, 28, 143, 388, 23, 374, 905, 942] values = [71, 15, 100, 37, 77, 28, 71, 30, 40, 22, 28, 39, 43, 61, 57, 100, 28, 47, 32, 66, 79, 70, 86, 86, 22, 57, 29, 38, 83, 73, 91, 54, 61, 63, 45, 30, 51, 5, 83, 18, 72, 89, 27, 66, 43, 64, 22, 23, 22, 72, 10, 29, 59, 45, 65, 38, 22, 68, 23, 13, 45, 34, 63, 34, 38, 30, 82, 33, 64, 100, 26, 50, 66, 40, 85, 71, 54, 25, 100, 74, 96, 62, 58, 21, 35, 36, 91, 7, 19, 32, 77, 70, 23, 43, 78, 98, 30, 12, 76, 38] capacity = 2000 # 2. 建模：每件物品一个 0/1 布尔变量 model = cp_model.CpModel() xs = [model.new_bool_var(f"x_{i}") for i in range(len(weights))] # 3. 约束：总重量 <= 容量 model.add(sum(x * w for x, w in zip(xs, weights)) <= capacity) # 4. 目标：最大化总价值 model.maximize(sum(x * v for x, v in zip(xs, values))) # 5. 求解并输出 solver = cp_model.CpSolver() solver.solve(model) print("Optimal selection:", [i for i, x in enumerate(xs) if solver.value(x)]) print("Total packed value:", solver.objective_value)

运行结果（作者实测）：

Optimal selection: [2, 14, 19, 20, 29, 33, 52, 53, 54, 58, 66, 72, 76, 77, 81, 86, 93, 94, 96] Total packed value: 1161.0

⚡ 在作者的机器上，CP-SAT 从 $2^{100}$ 种可能中找出可证明的最优解只用了 0.01 秒。代码逐行看：布尔变量x_i表示"第 i 件物品是否打包"，一个线性不等式就是容量约束，一行maximize就是目标函数——这就是 CP-SAT 建模的全部套路。

第四步：读懂求解日志与状态，判断CP-SAT干得好不好

问题变大后，CP-SAT 不一定总能算出最优解，但它通常仍会给出一个满意解，并附上最优解下界（bound）。这时看日志就成了必备技能：

CP-SAT 搜索进度日志：绿色为目标值（Objective），红色为下界（Bound），两者靠拢即接近最优

• 开启进度日志只需一行：solver.parameters.log_search_progress = True
• 目标值与界快速靠拢 → 问题好解；长期不靠拢 → 考虑换建模方式或加大时间预算
• 完整解读方法见章节chapters/understanding_the_log.md

常用参数速查：时间限制与并行加速

CP-SAT 默认会自动利用所有 CPU 核心并行搜索。入门阶段只需要记住这几个参数（solver.parameters下设置）：

⚠️ 官方提示：只有max_time_in_seconds等少数参数适合新手，其余如决策策略等高级参数建议先不动。完整参数讲解在chapters/parameters.md。

CP-SAT Primer还能帮你做什么：从背包到排班、路径规划

背包只是冰山一角。CP-SAT 天然适合处理"一堆逻辑条件"的问题，项目里就有大量现成案例：

• 🗓️会议排程：在候选人空闲时段里为 4 场会议互不冲突地排时间——examples/meeting_schedule.png展示了排程结果
• 🚚车辆路径问题（VRP/TSP）：带容量约束的巡回路线优化，见examples/cvrp/cvrp_circuit.py
• 📦二维装箱/打包：矩形无旋转与可旋转两种建模，见evaluations/packing/solver/knapsack_wo_rotations.py
• 🩺护士排班：测试驱动开发风格求解排班约束，见examples/tdd/nurserostering/solver.py

CP-SAT 会议排程示例：蓝色为已排定的会议时段，红点为候选时间窗

新手常见疑问（FAQ）

Q1：CP-SAT 支持浮点数变量吗？不支持。CP-SAT 只有整数和布尔变量。需要小数时，把所有数据乘以 100（保留两位精度）变成整数即可，例如 2.35 用 235 表示。

Q2：模型无解（INFEASIBLE）怎么办？说明约束过强，互相矛盾。排查技巧：先只保留一半约束定位冲突，或把"必须满足"的约束改成软约束参与惩罚。

Q3：和 Gurobi、CPLEX 这类 MIP 求解器怎么选？逻辑约束多、布尔变量为主 → 优先 CP-SAT；连续变量多、依赖强线性松弛 → MIP 求解器更有优势。cpsat-primer的chapters/big_picture.md有全面的横向对比。

Q4：想系统学习，按什么顺序读？建议路径：chapters/installation.md→chapters/example.md→chapters/modelling.md（变量/约束/目标）→chapters/advanced_modelling.md（circuit、区间等高级约束）→chapters/parameters.md→chapters/understanding_the_log.md。进阶读者再看chapters/lns.md（大邻域搜索）和chapters/benchmarking.md（基准测试）。

总结：10分钟学会的核心要点

1. 安装：pip3 install -U ortools，一条命令搞定，建议常更新
2. 建模三要素：变量（new_bool_var/new_int_var）→ 约束（model.add）→ 目标（model.maximize/minimize）
3. 威力：100 件物品背包问题，$2^{100}$ 种组合，0.01 秒求出可证明最优解
4. 进阶：用max_time_in_seconds控时、看日志判断收敛，再深入高级建模章节

CP-SAT Primer 由德国 Braunschweig 理工学院的 Dominik Krupke 博士编写，内容在算法工程课程中实际使用并持续完善。如果你打算深入，可以克隆完整教程仓库浏览全部章节与 Notebook：

git clone https://gitcode.com/gh_mirrors/cp/cpsat-primer

现在，打开你的终端，跑起来第一个模型吧 🚀

【免费下载链接】cpsat-primerThe CP-SAT Primer: Using and Understanding Google OR-Tools' CP-SAT Solver项目地址: https://gitcode.com/gh_mirrors/cp/cpsat-primer