Repolode
d-krupke

d-krupke/cpsat-primer

一本讲解如何用 Google OR-Tools 的 CP-SAT 求解器建模并求解组合优化问题的开放教程。

Star
834
Fork
69
未关闭 Issue
9
最近提交
2个月前

这是什么?

CP-SAT Primer 是一本免费的类书籍教程,用于学习 Google OR-Tools 中的 CP-SAT 求解器。CP-SAT 基于约束编程与 SAT 技术,适用于组合优化问题。教程面向计算机专业学生和开发者,全文配有 Python 示例,并将 CP-SAT 与混合整数规划(MIP)求解器及其他优化工具进行了比较。

第一部分涵盖安装、第一个模型,以及变量、目标函数和约束的基础建模,还包括电路约束、区间约束、资源约束等高级约束、求解器参数设置,以及如何阅读求解日志。第二部分讨论工程实践,包括便于维护的代码组织方式、通过 API 提供优化服务、大邻域搜索启发式算法,以及模型基准测试。

本教程由 TU Braunschweig 的 Dominik Krupke 维护,采用 CC-BY 4.0 协议发布,并提供网页版本。

核心功能

  • 01涵盖 CP-SAT 基础,包括变量、目标函数以及线性和逻辑约束。
  • 02讲解电路约束、区间约束、不重叠约束等高级约束。
  • 03介绍如何设置求解时间限制、提示信息和并行参数。
  • 04讲解如何阅读求解日志,判断解的质量。
  • 05将 CP-SAT 与 MIP 求解器及其他优化技术进行对比。
  • 06提供 Python 代码示例,并包含大邻域搜索章节。

适用场景

  • 计算机专业学生学习组合优化。
  • 从 MIP 求解器迁移到 CP-SAT 构建排程或路径模型。
  • 基于 CP-SAT 构建可维护的优化服务接口。
  • 为实际问题对 CP-SAT 模型进行基准测试与调优。

快速上手

  1. 1

    使用 pip 安装 OR-Tools

    pip install -U ortools
  2. 2

    复制 README 中的背包问题示例并用 Python 运行

标签

常见问题

cpsat-primer 是什么?
一本讲解如何用 Google OR-Tools 的 CP-SAT 求解器建模并求解组合优化问题的开放教程。 CP-SAT Primer 是一本免费的类书籍教程,用于学习 Google OR-Tools 中的 CP-SAT 求解器。CP-SAT 基于约束编程与 SAT 技术,适用于组合优化问题。教程面向计算机专业学生和开发者,全文配有 Python 示例,并将 CP-SAT 与混合整数规划(MIP)求解器及其他优化工具进行了比较。
cpsat-primer 可以免费使用吗?用的什么许可证?
cpsat-primer 以 CC-BY-4.0 许可证开源。用于商业产品前,请先确认许可证条款。
cpsat-primer 还在维护吗?
半年内有更新。cpsat-primer 最近一次提交是在 2026年9月6日。
cpsat-primer 适合用来做什么?
计算机专业学生学习组合优化。 从 MIP 求解器迁移到 CP-SAT 构建排程或路径模型。 基于 CP-SAT 构建可维护的优化服务接口。 为实际问题对 CP-SAT 模型进行基准测试与调优。
cpsat-primer 怎么安装和运行?
使用 pip 安装 OR-Tools: pip install -U ortools 复制 README 中的背包问题示例并用 Python 运行
在哪里获取 cpsat-primer?
源代码和安装说明在 GitHub 上:https://github.com/d-krupke/cpsat-primer

概要由 AI 根据项目 README 生成;GitHub 数据每日更新。

相关项目