用隐式击中集法改进加权约束满足问题求解，效果稳定。
Empirical Evaluation of the Implicit Hitting Set Approach for Weighted CSPs
- 结合SAT与隐式击中集，优化低代价击中向量和高代价核心转换
- 32种实现中，合并代价函数并提取最大核心表现最稳健
- 适合需要稳定求解性能的加权约束问题研究者
SAT技术在众多领域表现出意外的有效性，但针对加权约束满足问题（WCSP），专用算法始终更优。目前未被充分研究的一种方法是将SAT与隐式击中集（IHS）结合。本文探索了现有基准算法的若干替代方案，主要借鉴相关布尔框架中的思路，针对IHS的两个核心组件——低代价击中向量计算与高代价核心转换——分别提出4种强度等级的变体。此外，还测试了代价函数合并的有效性。实验共评估32种不同实现方式。结果表明，对于WCSP而言，难以确定最优方案；但代价函数合并配合提取最大核心的策略展现出较强的鲁棒性。
原文摘要 · Abstract (English)
SAT technology has proven to be surprisingly effective in a large variety of domains. However, for the Weighted CSP problem dedicated algorithms have always been superior. One approach not well-studied so far is the use of SAT in conjunction with the Implicit Hitting Set approach. In this work, we explore some alternatives to the existing algorithm of reference. The alternatives, mostly borrowed from related boolean frameworks, consider trade-offs for the two main components of the IHS approach: the computation of low-cost hitting vectors, and their transformation into high-cost cores. For each one, we propose 4 levels of intensity. Since we also test the usefulness of cost function merging, our experiments consider 32 different implementations. Our empirical study shows that for WCSP it is not easy to identify the best alternative. Nevertheless, the cost-function merging encoding and extracting maximal cores seems to be a robust approach.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。