SEER: 使用监督学习控制 Energetic Reasoning

# 监督学习控制能量推理  
本文发表于 CP2014 里昂博士项目。  
来源：https://arxiv.org/html/2607.16523  
Sascha Van Cauwelaert¹, Michele Lombardi², and Pierre Schaus¹  Université Catholique de Louvain, Università di Bologna  

###### 摘要  

> 约束编程的主要优势之一是通过传播来缩小搜索空间。然而，传播是一把双刃剑：更强的剪枝能力以更大的计算时间为代价。对于每个约束，最佳传播器取决于具体实例，并可能在搜索过程中发生变化。文献中，机器学习（ML）技术和基于活动的启发式方法分别被用于（静态地）为一批问题选择传播器，以及（动态地）调整传播强度。我们提议整合这些工作，使用通过 ML 获得的 oracle 函数，来决定是否为目标约束运行复杂传播器。一系列设计选择使该方法灵活且易于嵌入最先进的求解器。本文重点研究为能量推理传播器构建 oracle 的可行性。实验表明，可以获得高预测精度，提供分类特征的建议，并强调构建此类 oracle 时需要解决的重要问题。

## 1 引言  

通过传播缩小搜索空间的能力是约束编程（CP）的显著特征之一，这使其能够解决复杂的组合问题。然而，传播是一把双刃剑：更强大的过滤算法能提供更高的值剪枝机会，但也会消耗更长的计算时间，无论是否实际实现额外传播，都必须付出这些时间代价。

例如，`cumulative` 约束广泛用于对具有不可中断活动的调度问题进行资源限制建模。该约束是 CP 中研究最深入的约束之一，拥有多种传播器。特别是，基于时间表的算法（如 SWEEP (?)）代表了计算复杂度轻量级的一端，时间复杂度为 O(n²)。已知时间表传播（TT）受能量推理（ER，见 (?)）支配，但 ER 在实践中很少使用，因为其算法时间复杂度更高——O(n³)——并且通常最终与时间表得到相同的域缩减。

然而，在某些实例中，ER 可以显著减少搜索树。在 BL 基准 (?) 上，当使用对开始变量进行二分搜索时，该传播器在约 65% 的实例上可将回溯次数减少一个数量级；当使用调度特定搜索——*SetTimes*，见 (?)——时，在约 88% 的实例上也是如此。每当一个约束拥有不同剪枝能力和复杂度的传播器时，就会出现类似行为。

最佳传播器取决于目标问题和实例的具体特性，并且远非容易选择。通常由模型设计者根据个人经验、直觉和试点测试来选择，结果好坏参半 (感兴趣的读者可参考 (?))。近年来，机器学习 (ML) 技术已被提出用于自动化决策 (?)，并取得了有前景的结果。然而，这种方法没有考虑搜索决策对传播器有效性的影响。这在 (?) 中已被认识到，作者提出通过基于求解器状态的启发式方法在运行时调整传播强度。不幸的是，设计和选择正确的启发式方法是一项复杂（且依赖问题）的任务。在 (?) 中引入了参数化一致性，其中将局部一致性属性与阈值参数进行比较，以便对不同值实施不同的一致性级别。还考虑了启发式方法来动态调整该参数。

*我们提议整合上述方法，使用通过 ML 获得的 oracle，在运行时预测运行特定约束的特定传播器是否会有益。该决策应基于约束作用域中变量的当前域，即传播器本身的输入*。例如，这样的 oracle（实际上是一个分类器）可用于决定在 TT 传播器达到不动点后是否运行 ER。与 (?) 相比，我们的方法可在搜索时调整传播级别。与 (?) 相比，它更少依赖问题，因为它在单个约束级别上运作。此外，使用 ML 免去了设计者寻找良好启发式规则的工作（尽管特征选择仍然是一个问题）。

在单个约束级别上工作使我们的方法易于在最先进的求解器上实现。此外，由于我们考虑的预测仅涉及单个传播器，因此当引入新传播算法时无需重新训练。最后，由于 oracle 输入不包含状态信息（当然除了域），该方法非常适合复杂搜索技术，如非时间顺序回溯和（更重要的是）大邻域搜索。

有效部署这种方法是一项雄心勃勃的事业。作为起点，本文研究为 ER 传播器构建 oracle 的可行性，我们使用缩写 SEER（监督学习控制能量推理，Supervised lEarning to control Energetic Reasoning）。特别地，我们专注于检测在 TT 达到不动点后运行 ER 是否会缩小域的问题。时间方面（例如传播量与求解时间缩减之间的权衡）留待未来研究。在本研究中，我们表明确实可以获得高预测率，提供关于如何定义良好训练集的指导方针，建议作为分类器输入的有效特征，并强调在 oracle 设计中要解决的关键问题。

## 2 背景与相关工作  

### 2.1 CP 与调度问题  

约束编程是一种解决约束满足问题（CSP）的技术。CSP 是一个三元组 ⟨X, D, C⟩，其中 X 是一组变量 x_i，D 是它们的域 D_i（通常是有限整数），C 是一组必须满足的约束 c_k。每个约束定义在一个变量子集 S(c_k)（称为作用域）上，并有一个关联算法（传播器），可以从 S(c_k) 中的变量上剪枝证明不可行的值。c_k 的传播器可以看作是函数：

π: (D_j | x_j ∈ S(c_k)) ↦ (D′_j | x_j ∈ S(c_k))   (1)
其中 (D_j | x_j ∈ S(C_k)) 是一个 n 元组，包含 S(c_k) 中变量的域。对于所有变量，必须满足 D′_j ⊆ D_j。非正式地说，传播器将一组域映射到它们的一个缩小版本。CSP 通常通过分支来解决，通过发布额外约束并触发其传播器。这会引起域缩减，可能唤醒其他传播器，直到达到不动点。优化可以通过在找到可行解后添加一个永久约束来实现，要求未来解具有更优的成本。

*资源约束项目调度问题* (RCPSP) 包括为活动集合 A 找到开始时间。每个活动 a_i 有固定工期 d_i，并对集合 R 中的每个资源 r_k 需求数量 r_{ik}。每个资源有有限容量 cap_k，活动之间可能由优先约束连接。目标是最小化最坏情况完成时间（makespan）。在 CP 中，RCPSP 通过为每个活动引入开始变量 s_i，并通过 `cumulative` 约束 (?) 对资源限制进行建模，该约束对每个资源 r_k 强制执行以下关系：

∑_{s_i ≤ t < s_i + d_i} r_{ik} ≤ cap_k    ∀ t = 0..eoh   (2)
即，不允许资源超用。术语 eoh 指最大可能结束时间，其中每个结束时间 e_i 对应 s_i + d_i。s_i 和 e_i 的边界有常规名称：est_i 和 lst_i 分别是最早和最晚开始时间，而 ect_i 和 lct_i 是最早和最晚完成（结束）时间。`cumulative` 约束是 CP 中研究最深入的约束之一，拥有多种传播器 (?) 。本文中，我们主要关注能量推理和（次要地）时间表传播。

*时间表传播器* 基于强制部分（即任务必须被处理的时间区间）进行推理。通过聚合所有活动的强制部分，我们可以获得最小资源消耗曲线。基于此信息，如果发现在最早开始时间 s̄_i 调度活动会超过最小消耗曲线中的可用容量，我们可以剪枝 s_i 的域。存在几种基于时间表的算法，复杂度为 O(n²) (?)。

*能量推理* 是一种基于给定时间区间内能量消耗概念的传播器。如果最小消耗大于该区间内提供的能量，则约束无法满足，或者至少可以进行一些边界调整。该算法运行时间为 O(n³)。注意，存在 O(n²) 的算法，它们无法进行边界调整，只能检测不一致性 (?)。然而，与 TT 和 ER 检查器的组合相比，使用经典 ER 算法仍能显著减小搜索空间：在 BL 实例上，使用二分搜索时约 45% 的实例实现了 3 倍的缩减，使用 *SetTimes* 时约 19% 的实例如此。

### 2.2 算法选择与传播  

我们考虑的问题与算法选择密切相关，即为解决给定问题选择最佳算法的活动，该问题首先在 (?) 中被形式化。自那时起，该领域受到了优化和 ML 社区的广泛关注，因此相关文献非常广泛且复杂。存在离线方法，依赖于问题特征来选择单个算法或一组算法（并行执行或按计划顺序执行）。在线方法可以在运行时调整选择，但会带来额外的开销问题。选择活动可能涉及挑选完全不同的算法或调整单个方法的参数。使用了多种 ML 技术，从简单的启发式规则到统计回归以及更复杂的技术，如决策树、人工神经网络、支持向量机和聚类。关于组合优化背景下算法选择的优秀概述（涵盖 Hydra 及其衍生品、SATzilla、ParamILS 和 ISAC），读者可参考 (?)。关于为学习问题选择最佳学习算法（所谓的元学习），(?) 中提供了很好的概述。

尽管关于算法选择的文献很广泛，但迄今为止只有少数工作涉及自动选择 CP 中的传播器（或调整一致性级别）。最早的例子是 (?)，作者提出了一种检测何时使用简单前向检查可以达到与弧一致性相同一致性级别的方法。该思想在 (?) 的方法中得到推广，该方法根据观察和预测的性能，在更简单（和更快）的一致性算法与更强大（和更慢）的一致性算法之间来回切换。最近，在 (?) 中提出了在“强”和“弱”传播之间切换的启发式规则。ER 的特殊情况在 (?) 中被考虑，其中使用了一个近似标准来估计 ER 的潜力。

使用机器学习方法选择传播器已在 (?) 中被考虑。在论文中，作者使用分类技术来选择在给定实例上用于 `alldiff` 约束的传播器（以及实现）。分类器在一组基准问题上训练，并接受实例的一般属性（例如 `alldiff` 约束的数量）和从其主图获得的更复杂特征作为输入。

## 3 设计过程  

### 3.1 问题定义  

给定一个目标约束 c_k 及其作用域 S(c_k) 中变量的当前域，我们考虑预测传播器 π 是否会导致某些剪枝（以合理概率）的问题。形式上，我们有兴趣设计一个 oracle 函数 O_π，使得：

O_π(D_i | x_i ∈ S(C_k)) = { true 如果某个值被剪枝
                         { false 否则

可以看到 O_π 具有与 π 相同的输入——参见方程 (1)。O_π 函数旨在用作传播器执行的守卫条件。

这种问题形式化有许多优点：首先，oracle *保证拥有足够的信息来做出正确猜测*。因此，挑战在于设计一个比传播器本身复杂度更低的 O_π 函数。其次，如果为该约束引入新的传播器，则必须训练新的 oracle，但*现有 oracle 完全不需要修改*。第三，oracle *可以在搜索过程中的任何时刻检查*，使设计者完全自由地组合传播器（只要考虑 oracle 的出错可能性）。更重要的是，这也使得该方法非常适合用于复杂搜索策略和大邻域搜索。

对于一组传播器，最简单的组合方案是运行一个轻量级算法（甚至只是一个检查器）直到达到不动点，然后仅在 O_π 返回 true 时运行一次更复杂传播器的单次迭代。这个简单的想法类似于 (?) 中使用的想法。如前所述，本文考虑为 ER 构建 oracle 函数的特殊情况，该 oracle 在 TT 传播达到不动点后被咨询。

通常，我们建议使用 ML 技术来为复杂传播器获取 oracle 函数 O_π。在此背景下，获取该函数需要：1) 构建具有代表性的训练集；2) 为分类器选择特征（基于变量域和静态信息）；3) 选择分类技术，然后训练和评估 ML 模型。

在下文中，我们将详细讨论这三个步骤，重点关注调查*准确* oracle 函数的可行性。在进行之前，值得注意，通过将时间方面（例如传播时间）纳入 oracle 定义，应能提高我们方法的有效性。这留待