限制条件优化

约束优化或 约束编程 (CP) 命名，用于从大量候选方案中确定可行的解决方案，问题可以建模 许多科学和工程学科中都存在 CP 问题。（“编程”一词有点不恰当，类似于“计算机”曾经表示“会计算的人”的意思）。此处的“编程”是指安排规划，而不是使用计算机语言进行编程。）

CP 基于可行性（找到可行的解决方案）而非优化（找出最佳解决方案），并且侧重于约束和变量，而非目标函数。事实上，CP 问题可能甚至没有目标函数 - 目标是通过为问题添加约束条件，将大量可能的解决方案缩小为更易于管理的子集。

一个非常适合 CP 的问题示例是员工调度。当持续运营的公司（例如工厂）需要为员工制定每周时间表时，就会出现这个问题。举一个非常简单的例子：某公司每天有三个班次，每班 8 小时，每天为四名员工中的三名安排不同的班次，同时给第四个员工休息日。即使在这样小的情况下，可能的时间表数量也非常庞大：每天可能有 4! = 4 * 3 * 2 * 1 = 24 名可能的员工班次，因此每周可以分配的员工数超过 4 亿。通常情况下，还有其他限制会减少可行解决方案的数量，例如，每位员工每周至少工作天数。当您添加新的约束条件时，CP 方法会跟踪哪些解决方案仍然可行，这使其成为解决大型实际调度问题的强大工具。

CP 在世界各地拥有一个非常活跃的广泛社区，这里有专门的科学期刊、各种会议以及各种不同的解析技术。CP 已成功应用于规划、调度以及众多具有异构约束的其他领域。

工具

Google 提供了几种解决 CP 问题的方法：

如果您的问题可以使用线性目标和线性约束进行建模，则表示您的问题属于线性规划问题，应考虑使用 MPSolver。（不过，即使路线问题可以用线性模型表示，我们的车辆路线库通常也能妥善解决。）

示例

下一部分将介绍 CP-SAT 求解器，它是约束编程的主要 OR 工具求解器。（SAT 代表“可满足性”：求解器使用各种技术以及 CP 方法来解决 SAT 问题。）

以下是一些非常适合 CP-SAT 求解器的调度问题示例：

两个经典的 CP 问题是 N 皇后问题和密码谜题。