#主题/PBO

[!tldr]文章链接在本工作中，我们重点关注提高 SLS 求解 PBO 的性能。

[!tldr]文章链接串行的算法中，引入了动态评分策略后，在并行的策略结合了种群的概念，引入了解池，通过共享高质量解与变量的极性密度（更倾向是 0/1）提高了跳出局部最优的能力 ParLS-PBO: A Parallel Local Search Solver for Pseudo Boolean Optimization [!abstract]-As a broadly applied technique in numerous optimization problems,

[!tldr]文章链接 与 代码链接本文和 是同年的文章，因此没有对比，这篇文章的 看了一下是不如 的，尤其是 300s 中 MWCB 和 SAP，NuPBO 能够全部都比 好，但本文有一些还是不如 LS-PBO，甚至在 中直接注明了 DeciLS-PBO 被 NuPBO 和 DLS-PBO 支配了 DeciLS-PBO: an Effective Local Search Method for Pseudo-Boolean Optimization [!abstract]-

[!tldr]文章链接提出了一种局部搜索求解 PBO 的框架，主要的思路就是把优化转为判定，由此可以使用 SAT 局部搜索求解器的思路，通过对约束加权（惩罚值），并由此进行打分函数的设计，从而指导启发式算法工作本文后续的改进版有：， ， Efficient Local Search for Pseudo Boolean Optimization [!abstract]-Pseudo-Boolean Optimization (PBO) can be used to model

[!tldr]文章链接本文提出了一种针对 局部 基数约束的局部搜索算法 LS-ECNF ，通过 ECNF 的形式，可以避免将基数约束编码为 SAT，从而获取更好的求解性能本文的后续改进为 ，值得注意的是，本文提出的 基数约束 本质上是一种特殊 形式 Extended Conjunctive Normal Form and An Efficient Algorithm for Cardinality Constraints [!abstract]Satisfiability (S

[!tldr]文章链接主要的贡献为：将 PBO 问题编码为 QAOA 的形式将 QAOA 分割为子问题进行分布式求解 Local to Global: A Distributed Quantum Approximate Optimization Algorithm for Pseudo-Boolean Optimization Problems [!abstract]-With the rapid advancement of quantum computing, Quant