用机器学习判断何时运行复杂约束传播器，提升求解效率。
SEER: Supervised Learning to Control Energetic Reasoning
- 用机器学习构建决策函数，动态决定是否启用复杂传播器。
- 实验显示预测准确率高，能有效减少不必要的计算。
- 适合想优化约束求解器性能的研究者与工程师。
约束编程的一大优势在于通过传播机制缩小搜索空间，但传播越强，计算开销越大。针对不同问题实例，最佳传播器可能不同，且在搜索过程中可能变化。现有研究分别采用机器学习和基于活跃度的启发式方法，静态选择传播器或动态调整传播强度。本文提出融合二者：利用机器学习构建一个‘可信函数’，决定是否对特定约束运行复杂传播器。该方法设计灵活，易于集成到主流求解器中。本文重点验证为能量推理（Energetic Reasoning）传播器构建此类可信函数的可行性。实验表明可获得高预测准确率，给出关键特征选择建议，并揭示构建该函数时需关注的关键问题。
原文摘要 · Abstract (English)
One of the main strengths of Constraint Programming is the ability to reduce the search space via propagation. However, propagation is a double-edged sword, with more pruning power coming at the price of larger computation time. For each problem constraint, the best propagator depends on the specific instance and may change at search time. In the literature, Machine Learning (ML) techniques and activity-based heuristics have been applied respectively for choosing (statically) the propagators for a batch of problems and to adapt (dynamically) the propagation strength. We propose to merge those efforts by using an oracle function, obtained via ML, to decide whether to run complex propagators for a target constraint. A combination of design choices makes the approach flexible and easy to embed in state-of-the-art solvers. In this paper, we focus on investigating the feasibility of building an oracle for the Energetic Reasoning propagator. Our experiments show that high prediction accuracy can be obtained, provide suggestions for classification features, and highlight important issues to address when building such an oracle.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。