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-primerCP-SAT Primercpsat-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(fx{solver.value(x)}, y{solver.value(y)}) # x0, y30 注意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(fx_{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求解时间上限大实例必设如 60relative_gap_limit相对间隙容忍度0.01表示误差 1% 内即停num_workers并行搜索线程数默认自动可显式设为核心数log_search_progress输出进度日志调试时开启True⚠️ 官方提示只有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.pyCP-SAT 会议排程示例蓝色为已排定的会议时段红点为候选时间窗新手常见疑问FAQQ1CP-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.mdcircuit、区间等高级约束→chapters/parameters.md→chapters/understanding_the_log.md。进阶读者再看chapters/lns.md大邻域搜索和chapters/benchmarking.md基准测试。总结10分钟学会的核心要点安装pip3 install -U ortools一条命令搞定建议常更新建模三要素变量new_bool_var/new_int_var→ 约束model.add→ 目标model.maximize/minimize威力100 件物品背包问题$2^{100}$ 种组合0.01 秒求出可证明最优解进阶用max_time_in_seconds控时、看日志判断收敛再深入高级建模章节CP-SAT Primer 由德国 Braunschweig 理工学院的 Dominik Krupke 博士编写内容在算法工程课程中实际使用并持续完善。如果你打算深入可以克隆完整教程仓库浏览全部章节与 Notebookgit 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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-primerCP-SAT Primercpsat-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(fx{solver.value(x)}, y{solver.value(y)}) # x0, y30 注意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(fx_{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求解时间上限大实例必设如 60relative_gap_limit相对间隙容忍度0.01表示误差 1% 内即停num_workers并行搜索线程数默认自动可显式设为核心数log_search_progress输出进度日志调试时开启True⚠️ 官方提示只有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.pyCP-SAT 会议排程示例蓝色为已排定的会议时段红点为候选时间窗新手常见疑问FAQQ1CP-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.mdcircuit、区间等高级约束→chapters/parameters.md→chapters/understanding_the_log.md。进阶读者再看chapters/lns.md大邻域搜索和chapters/benchmarking.md基准测试。总结10分钟学会的核心要点安装pip3 install -U ortools一条命令搞定建议常更新建模三要素变量new_bool_var/new_int_var→ 约束model.add→ 目标model.maximize/minimize威力100 件物品背包问题$2^{100}$ 种组合0.01 秒求出可证明最优解进阶用max_time_in_seconds控时、看日志判断收敛再深入高级建模章节CP-SAT Primer 由德国 Braunschweig 理工学院的 Dominik Krupke 博士编写内容在算法工程课程中实际使用并持续完善。如果你打算深入可以克隆完整教程仓库浏览全部章节与 Notebookgit 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考