将两种启发式搜索方法结合,实现持续优化的求解器。
Anytime Cooperative Implicit Hitting Set Solving
- 融合下界与上界搜索,在多线程中共享核心信息。
- 在三个基准测试中均优于独立使用任一方法。
- 具备实时优化能力,适合需要渐进解的场景。
隐式击中集(HS)方法在MaxSAT、伪布尔优化等布尔框架中表现优异。最近,该方法也被应用于类似的加权约束满足问题(Weighted CSP)框架,通过代价函数合并展现潜力。传统HS聚焦于提升下界(HS-lb),但如伪布尔优化所示,也可用于提升上界(HS-ub)。本文同时考虑两种方法,并在多线程架构中结合:双方可共享由对方发现的核心,产生协同效应。所提出的算法(HS-lub)在所有测试中均显著优于单独使用任一方法。更重要的是,HS-lub具有良好的任意时间行为,执行过程中优化差距持续缩小。我们在加权CSP框架上测试该方法,结果显示,即使是最简单的实现,有时也超越了更复杂的先进工具Toulbar2的并行混合最佳优先搜索方案。
原文摘要 · Abstract (English)
The Implicit Hitting Set (HS) approach has shown to be very effective for MaxSAT, Pseudo-boolean optimization and other boolean frameworks. Very recently, it has also shown its potential in the very similar Weighted CSP framework by means of the so-called cost-function merging. The original formulation of the HS approach focuses on obtaining increasingly better lower bounds (HS-lb). However, and as shown for Pseudo-Boolean Optimization, this approach can also be adapted to compute increasingly better upper bounds (HS-ub). In this paper we consider both HS approaches and show how they can be easily combined in a multithread architecture where cores discovered by either component are available by the other which, interestingly, generates synergy between them. We show that the resulting algorithm (HS-lub) is consistently superior to either HS-lb and HS-ub in isolation. Most importantly, HS-lub has an effective anytime behaviour with which the optimality gap is reduced during the execution. We tested our approach on the Weighted CSP framework and show on three different benchmarks that our very simple implementation sometimes outperforms the parallel hybrid best-first search implementation of the far more developed state-of-the-art Toulbar2.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。