让传播器学会排序：学习式优先级提升约束求解效率

约束编程（Constraint Programming, CP）求解器的性能，很大程度上取决于传播器（propagator）的执行顺序。然而，主流求解器（如 Choco）通常依赖固定、手工设计的启发式规则来分配传播器优先级。近期一项研究提出用机器学习方法，从问题实例的静态特征中学习依赖实例的传播器优先级，并在 XCSP3 基准上验证了该方法的有效性。

问题：传播器顺序为何重要？

在约束编程中，传播器负责根据约束条件缩减变量域，而搜索过程则依赖这些缩减来剪枝。传播器的执行顺序会影响传播的效率和求解时间。传统上，求解器使用手工调优的固定优先级，例如优先执行某些类型的约束。这种固定策略忽略了具体问题实例的结构特征，难以适应不同问题类的差异。

该研究将传播器优先级分配建模为**学习排序（learning-to-rank）**问题：给定一个实例，模型需要为其中所有传播器输出一个优先级排序。挑战在于，单个传播器的最优优先级无法直接观测，但一个优先级分配的整体质量可以通过求解器运行时间来衡量。这属于典型的弱监督学习场景。

约束编程中的传播与搜索：约束编程求解器通常交替执行两个阶段——传播（propagation）和搜索（search）。传播阶段，每个约束对应的传播器根据当前变量域移除不可能的值（即缩减变量域），这一过程会反复进行直到达到不动点。搜索阶段则通过分支策略（如选择变量和值）做出决策，进一步缩小问题空间。传播器缩减变量域的能力直接决定了搜索树的剪枝效果：域缩减越充分，搜索需要探索的节点越少。因此，传播器的执行顺序不仅影响单次传播的效率，还通过改变传播的收敛速度间接影响整体求解时间。不同的传播器可能相互触发，形成传播链，顺序不同会导致中间状态的差异，进而影响最终缩减的域。这就是为什么启发式地安排传播器顺序成为一个值得优化的决策问题。

方法：自注意力模型与运行时偏好

研究团队设计了一个基于自注意力（self-attention）的模型，联合为实例中出现的所有传播器打分。模型输入是每个传播器的静态特征（如约束类型、变量数量等），通过自注意力机制捕捉传播器之间的交互关系，最终输出每个传播器的得分。

训练数据通过随机化传播器优先级并记录求解器运行时间来生成。对于同一实例，不同的随机优先级会产生不同的运行时间；模型从这些运行时间中提取成对偏好（运行时间更短的优先级分配更优），并使用基于 Plackett-Luce 的排序损失进行训练。这样，模型学习到的是“哪种排序更可能带来更短的求解时间”，而非直接拟合每个传播器的绝对优先级。

预测得到的排序会映射到 Choco 求解器的离散优先级层级，并在搜索开始前注入。整个过程不修改 Choco 的传播或搜索算法，仅调整传播器优先级，因此具有较好的通用性和低侵入性。

Plackett-Luce 模型与排序损失：Plackett-Luce 模型是一种用于建模排序数据的概率模型，常用于学习排序（learning-to-rank）任务。它假设存在一个潜在的“效用值”对应每个项目，给定一个项目集合，排序的概率与这些效用值的指数成正比。具体地，对于排序 π，其概率为 ∏{i=1}^{n} exp(s{π(i)}) / ∑{j=i}^{n} exp(s{π(j)})，其中 s 是模型输出的得分。在本研究中，模型为每个传播器输出一个得分，Plackett-Luce 损失鼓励得分高的传播器排在前面，使得整体排序更可能产生较短的运行时间。训练时，通过比较同一实例下不同随机优先级产生的运行时间，构造出成对偏好（运行时间短的排序优于运行时间长的排序），然后最大化这些偏好排序的似然。这种方法不需要每个传播器的绝对优先级标签，仅需相对比较，因此非常适合弱监督场景。

实验：在 XCSP3 上的效果

研究在 XCSP3 基准实例上进行了评估。实验选取了 698 个被问题类标记为最难的测试实例，对比学习到的优先级与 Choco 默认优先级的表现。主要结果包括：

• 求解数量提升：学习优先级将成功求解的实例数从 634 提升到 654。
• 中位运行时间降低：中位求解时间减少了 27.93%。
• 聚合惩罚运行时间（PAR1）降低：PAR1 指标下降了 12.65%。

这些结果表明，即使是简单的学习式优先级调整，也能在困难实例上带来显著的性能收益。研究还观察到，改进幅度因问题类而异，某些问题类受益更大，而另一些则变化不明显。

PAR1 与中位运行时间：PAR1（Penalized Average Runtime with 1 second penalty）是评估求解器性能的常用指标，特别适用于存在未解决实例的基准测试。对于每个实例，若求解器在给定时间限制内成功求解，则记录实际运行时间；若超时或失败，则记为时间限制的倍数（通常为时间限制的 2 倍或一个固定惩罚值）。PAR1 是所有实例运行时间的平均值，其中未解决实例被赋予惩罚值。因此，PAR1 同时反映了求解速度和鲁棒性：降低 PAR1 意味着要么更快地求解已解决实例，要么解决了更多困难实例。中位运行时间则关注已解决实例的典型性能，不受极端值影响。这两个指标结合使用，能更全面地评估传播器优先级学习的效果。

简单策略融合：学习与默认的切换

由于不同问题类的改进程度不一致，研究者进一步尝试了一种简单策略：根据实例特征，在“学习到的优先级”和“默认优先级”之间进行选择。实验显示，这种选择策略能够进一步增加求解实例的数量，说明学习式优先级并非在所有情况下都优于默认策略，而动态选择可以兼顾两者优势。

这一发现也提示，实际部署时可能需要一个轻量级的元决策层，根据实例的静态特征决定是否采用学习到的排序。

意义与局限

该工作的核心贡献在于将传播器优先级学习形式化为排序问题，并利用求解器运行时间作为弱监督信号，避开了难以直接获取的传播器级标签。方法不修改求解器内核，易于集成到现有 CP 求解器中。

不过，目前实验仅限于 Choco 求解器和 XCSP3 基准，泛化到其他求解器（如 Gecode、OR-Tools）和更广泛的问题领域仍需验证。此外，训练过程需要大量随机优先级下的运行时间数据，计算开销不可忽视。未来工作可能会探索更高效的训练信号以及跨求解器的迁移学习。

总体而言，这项研究为约束编程中的启发式学习提供了新思路，展示了机器学习在优化求解器内部决策方面的潜力。