论文标题
部分可观测时空混沌系统的无模型预测
DPMS: An ADD-Based Symbolic Approach for Generalized MaxSAT Solving
论文作者
论文摘要
布尔·麦克斯萨特（Boolean Maxsat）以及诸如Min-Maxsat和Max Hybrid-Sat之类的广义配方都是布尔推理的基本优化问题。 MaxSat的现有方法已成功地以CNF格式求解基准。但是，他们缺乏处理1）（非CNF）混合限制的能力，例如XORS和2）本地概括的MaxSat问题。为了解决这个问题，我们提出了一种新型的动态编程方法，用于用混合约束解决通用的MaxSAT问题 - 基于代数决策图（添加），称为\ emph {dynamic-programpramming-maxsat}或简称DPMS。借助Adds的功能和（分级）项目-Join-Tree Builder，我们的多功能框架接受了CNF-Maxsat的许多概括，例如MaxSat，Min-Maxsat和Minsat具有混合约束。此外，DPM在宽度较低的实例上表现得很好。经验结果表明，DPM能够快速解决某些问题，而基于各种技术的其他算法都失败了。因此，DPMS是一个有前途的框架，并开设了一项新的研究系列，该研究将来会有更多的调查。
Boolean MaxSAT, as well as generalized formulations such as Min-MaxSAT and Max-hybrid-SAT, are fundamental optimization problems in Boolean reasoning. Existing methods for MaxSAT have been successful in solving benchmarks in CNF format. They lack, however, the ability to handle 1) (non-CNF) hybrid constraints, such as XORs and 2) generalized MaxSAT problems natively. To address this issue, we propose a novel dynamic-programming approach for solving generalized MaxSAT problems with hybrid constraints -- called \emph{Dynamic-Programming-MaxSAT} or DPMS for short -- based on Algebraic Decision Diagrams (ADDs). With the power of ADDs and the (graded) project-join-tree builder, our versatile framework admits many generalizations of CNF-MaxSAT, such as MaxSAT, Min-MaxSAT, and MinSAT with hybrid constraints. Moreover, DPMS scales provably well on instances with low width. Empirical results indicate that DPMS is able to solve certain problems quickly, where other algorithms based on various techniques all fail. Hence, DPMS is a promising framework and opens a new line of research that invites more investigation in the future.
