约束规划
- 提出者
- Rossi, van Beek & Walsh
- 年份
- 2006
- 类型
- Declarative combinatorial optimization
- 类别
- Mathematical programming
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
约束规划(CP)是一种声明式优化范式,其中问题被表述为一组变量、有限域和约束,求解器系统地搜索满足所有约束的赋值。Rossi、van Beek 和 Walsh 在其 2006 年的《约束规划手册》中对其进行了全面形式化,CP 将传播式剪枝与智能回溯搜索相结合,以解决调度、规划和配置领域的组合问题。
方法背后的直觉
将 CP 视为填写一个复杂的拼图:每个单元格都是一个具有一组合法值的变量,拼图的每条规则都是一个约束。CP 不是盲目猜测,而是利用规则在填入一个单元格时立即消除相邻单元格中不可能的值。这种传播极大地缩小了搜索空间,因此求解器只探索可能的组合——仅在遇到死胡同时回溯和修正。
历史学
约束规划起源于 20 世纪 70 年代的人工智能研究,早期工作由 Montanari 和 Mackworth 在约束满足方面进行。通过弧一致性算法、全局约束以及 CHIP 和 ILOG Solver 等实际求解器的开发,它在 80 年代和 90 年代日趋成熟。该领域由 Rossi、van Beek 和 Walsh 在 2006 年的《约束规划手册》中权威性地整合,该手册至今仍是权威参考,涵盖了组合优化的理论、算法和应用。
何时使用
约束规划最适合具有复杂、异构约束的组合问题——调度、排课、配置和路线规划——其中可行性与最优性同等重要。它假定问题可以用离散或可枚举的变量域进行建模。CP 对于连续优化或大规模线性规划效果较差,这些问题通常由线性规划或混合整数规划求解器主导。当约束高度结构化且传播可以剪枝搜索空间的很大一部分时,CP 的性能优于通用元启发式方法。
局限与注意事项
- 可扩展性:最坏情况下的指数级搜索使得 CP 在具有弱传播的非常大的实例上速度较慢。
- 需要良好的建模:糟糕的变量/值排序启发式或缺失的全局约束会导致不必要的巨大搜索树。
- 连续域:CP 本质上是为离散域设计的;连续问题需要专门的扩展或混合方法。
- 求解器专业知识:有效使用需要熟悉约束建模技术和特定于求解器的全局约束库。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 声明式建模:复杂的现实世界规则直接表示为约束,而无需指定搜索过程。
- 强大的剪枝:约束传播及早消除了不可行区域,通常将搜索减少几个数量级。
- 处理异构约束:逻辑、算术、全局和用户定义的约束在单个模型中自然共存。
- 保证完整性:求解器要么找到最优解,要么证明不可行,这与启发式方法不同。
应用
- 员工和护士排班:在满足可用性、劳动法和技能约束的同时,将员工分配到班次。
- 排课:在满足教室容量、教师可用性和课程设置约束的同时,构建大学或学校的课程表。
- 配置:在兼容性和资源约束下,从组件目录中组装产品配置(计算机、车辆)。
- 车辆路线规划和物流:在满足时间窗口、车辆容量和驾驶员法规的同时,规划配送路线。
- 组合拍卖和资源分配:在互斥和预算约束下,将资源分配给投标人或任务。
使用方式
使用方式
问题被编码为一个约束满足问题三元组,由变量 X、它们的有限域 D 和一组约束 C 组成。每个变量 x_i 可以被赋值为其域 D_i 中的任何值。约束定义了变量子集之间允许的值组合,将现实世界的规则——容量限制、优先关系、资源冲突——转化为求解器可以推理的数学结构。
公式
\text{CSP} = \langle X, D, C \rangle \quad X = \{x_1, x_2, \ldots, x_n\},\; D = \{D_1, D_2, \ldots, D_n\}在搜索之前和搜索期间,求解器应用弧一致性和其他局部一致性算法来剪枝不能参与任何有效解的域值。对于每对受约束的变量,弧一致性会从一个变量的域中移除另一个变量域中不存在支持值的那些值。每次赋值后,这种传播都会被反复触发,从而极大地减小了有效的搜索空间。
公式
\text{AC}(x_i, x_j): \forall a \in D_i,\; \exists b \in D_j \text{ s.t. } c_{ij}(a, b) \text{ holds}求解器选择一个未赋值的变量——通常使用最小剩余值或度数等启发式方法——并暂时为其域的剪枝值赋一个值。再次运行传播;如果检测到矛盾(空域),求解器将回溯到最近的选择点并尝试替代值。回溯和记录不良组合可以进一步加速从失败中恢复。
公式
x_i \leftarrow a_i \in D_i,\quad \text{propagate},\quad \text{if fail: backtrack and reassign}当所有变量都被赋值且与每个约束一致时,完整的赋值 S* 就构成了一个解。对于优化问题,目标函数指导搜索以找到最佳可行解,并且分支定界策略随着找到更好的解而逐步收紧界限,直到认证全局最优解或达到时间限制。
公式
S^* = \{(x_1, a_1^*), \ldots, (x_n, a_n^*)\} : \forall c \in C,\; c(a_1^*, \ldots, a_n^*) = \text{true}常见陷阱
- 用冗余或冲突的约束过度约束模型会导致求解器错误地报告不可行。
- 忽略全局约束(例如,alldifferent、cumulative)会错过专门算法免费提供的传播机会。
- 忽略搜索启发式方法而依赖默认的变量/值排序可能在病态排序上浪费指数级时间。
- 混淆约束满足与优化:忘记添加目标函数和界限收紧只会得到第一个可行解,而不是最优解。
常见问题
约束规划与整数线性规划有何不同?
两者都解决组合问题,但 ILP 要求所有约束和目标都是线性的,从而能够获得有效的 LP 松弛界限。CP 不施加此类线性要求,而是依赖约束传播和系统搜索。CP 更自然地处理复杂的逻辑和全局约束,而 ILP 在具有强大线性结构和大量变量的问题上通常具有更好的可扩展性。
什么是全局约束及其重要性?
全局约束是关于任意数量变量的高级约束——例如,alldifferent(所有变量取不同值)或 cumulative(任何时间的资源使用量不超过容量)。它们之所以重要,是因为求解器为每个全局约束实现了专用、高效的传播算法,实现了比分解相同条件为多个二元约束强得多的剪枝效果,而后者会留下大量搜索空间未被探索。
约束规划能找到最优解还是只能找到可行解?
CP 可以通过将可行性搜索与目标函数相结合来找到最优解。求解器使用分支定界:一旦找到可行解,它会添加一个约束,要求任何后续解都必须严格更好,并持续进行,直到无法改进为止。这证明了最优性。如果运行时间受限,则返回迄今找到的最佳解作为近似值。
相关方法
参考文献
Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier.
ISBN:978-0-444-52726-4已复制。