arXiv · cs.AI · Hieu Truong Xuan, Tuyen Kieu Van, Khanh To Van · 4 小时前模型评分19
面向梯形结构至多K基数约束集的 SAT 编码
SAT Encoding for Set of At-Most-K Cardinality Constraints with Ladder Shape
导读
研究提出首个针对梯形至多K基数约束（Ladder AMK，k>1）的 SAT 编码方法，将约束序列分块后整体编码，并用顺序计数器（Sequential Counter）连接相邻块。相比基于 BDD 的既有编码，新方法所需变量和子句更少，求解时间显著缩短。在反带宽问题和护士排班问题上的实验显示，该编码优于其他编码及约束规划、混合整数规划求解器。
分类置信度
中 · 待人工复核
- 只有单一媒体来源，需要人工复核。
来源级别：媒体与个人
事件类型：研究发布
证据摘录
- “This paper presents a novel SAT encoding designed to represent a sequence of At-Most-K cardinality constraints arranged in a ladder-like structure, referred to as the Ladder AMK constraint.”
来源：arXiv · cs.AI · arxiv.org