Mar, 2024

通过实时性能分析来更好理解和配置 MaxSAT 局部搜索求解器

PDF
TL;DR本文介绍了一种使用经验累积分布函数来比较 MaxSAT 局部搜索求解器在多个问题实例和不同时间预算下的任意时刻性能的方法，实证评估结果显示求解器的性能存在差异，并且在不同的运行时间下求解器的优势和劣势会有所调整，同时，这项工作还证明了以任意时刻性能作为成本函数进行超参数优化的方法能够得到更好的局部搜索参数设置。
发现论文，激发创造
  • 使用连续运行分布预测 SAT 局部搜索的并行加速

    本文通过分析顺序版本算法的运行时行为，提出了一种评估给定算法并行性能的框架，并将此方法应用于研究两种 SAT 局部搜索求解器的并行性能，结果表明模型能够准确预测性能并展示了不同情况下局部搜索求解器的运行时分布。

    Jan, 2024

  • 利用 MaxSAT 求解器的配置

    本篇论文探讨了如何利用 MaxSAT solver 的不同参数配置并进行实验，特别地，我们将多种非竞争性求解器配置相结合以获得更好的解决方案。

    Jun, 2023

  • 正式化运行时分布的偏好

    该论文旨在通过形式化运行时分布的喜好来解决在算法选择中的竞争。我们提出了一种基于效用理论的方法，描述了算法偏好的评分函数，这些函数依赖于解决问题的价值如何随时间降低以及满足的时间分布。我们展示了实用程序函数的例子，并展示了如何利用最大熵方法来建模未规定的时间分布，最后，我们展示了如何从运行时样本中高效估计算法的预期效用。

    May, 2022

  • 给定计算时间限制的伪布尔优化的自动算法选择

    构建适用于 NP-Hard 的 Pseudo-Boolean 优化问题的任意时刻元求解器，明显提高了性能，并改进了在组合求解器组合中性能表现最好的单个求解器 Gurobi 的成功率。

    Sep, 2023

  • 多目标组合优化问题的高效任意时刻算法

    提出了一个新的精确的任意时刻算法，通过三个新颖的思想来增强多目标组合优化问题的任意时刻行为，并在多个性能度量上的综合实验研究中表明优于以前的算法。

    Feb, 2024

  • Cakewalk Sampling

    利用鲁棒的学习算法，我们研究了如何适应任意目标函数的采样分布以寻找良好的局部最优解。我们的研究结果表明，我们的自适应采样器可以为实践中出现的组合优化问题提供有效的解决方案。

    Feb, 2018

  • 探索 SLS 算法中长尾运行时间的理解

    本论文研究了使用随机局部搜索解决基于满足性问题的 SAT 问题的流行范式，以及通过学习逻辑蕴含来改善求解器性能，并提出了一种生成逻辑等价问题形式的方法，进一步深入研究学习逻辑蕴含如何影响 SLS 运行时间的问题。

    Oct, 2022

  • 组合嵌套 Monte Carlo 与局部搜索方法解决 MaxSAT 问题

    本文介绍了针对最大可满足性问题提出的 UCTMAXSAT 算法，探讨了两种算法变化对算法性能的影响，提出了使用静态翻转限制并动态设置预算来达到相似性能的建议。

    Feb, 2023

  • 利用远见概率采样提升本地搜索 MaxSAT 求解器的通用策略

    本文提出了一种名为 FPS 的策略，通过考虑连续翻转一对变量的好处来替换单一翻转机制，以提高本地搜索算法的效率，解决了局部最优解品质较低的问题，并通过最佳取样的方法避免了局部最优解，实验表明该方法极大地提高了最先进的 (W) PMS 解算器的性能。

    Aug, 2021

  • 可配置的 SAT 求解器挑战 (CSSC)

    Configurable SAT Solver Competition (CSSC) compares solvers by the performance they achieved after a fully automated configuration step to solve combinatorial problems, particularly propositional satisfiability problem (SAT), by tuning solver parameters, with CSSC 2013 and 2014 being reported.

    May, 2015