A Branch-and-Bound Algorithm for Extracting Smallest Minimal Unsatisfiable Formulas

机译：提取最小最小不满足公式的分支定界算法

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

We tackle the problem of finding a smallest-cardinality MUS (SMUS) of a given formula. The SMUS provides a succinct explanation of infeasibility and is valuable for applications that rely on such explanations. We present a branch-and-bound algorithm that utilizes iterative MAXSAT solutions to generate lower and upper bounds on the size of the SMUS, and branch on specific subformulas to find it. We report experimental results on formulas from DIMACS and DaimlerChrysler product configuration suites.

机译：我们解决了找到给定公式的最小基数MUS（SMUS）的问题。 SMUS提供了不可行的简洁解释，对于依赖于这种解释的应用程序非常有价值。我们提出了一种分支定界算法，该算法利用迭代MAXSAT解决方案生成SMUS大小的上限和下限，并在特定子公式上分支以找到它。我们报告来自DIMACS和戴姆勒克莱斯勒产品配置套件的公式的实验结果。

著录项

来源
《International Conference on Theory and Applications of Satisfiability Testing(SAT 2005); 20050619-23; St Andrews(GB)》|2005年|P.467-474|共8页
会议地点 St Andrews(GB)
作者
Maher Mneimneh; Ines Lynce; Zaher Andraus; Joao Marques-Silva; Karem Sakallah;
展开▼
作者单位

University of Michigan;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类计算数学;理论、方法;
关键词

相似文献

外文文献
中文文献
专利

1. A branch and bound algorithm for extracting smallest minimal unsatisfiable subformulas [J] . Mark Liffiton, Mahcr Mneimnch, Ines Lynce, Constraints . 2009,第4期

机译：分支定界算法，用于提取最小的最小不满足子公式
2. On good algorithms for determining unsatisfiability of propositional formulas [J] . John Franco, Ram Swaminathan Discrete Applied Mathematics . 2003,第2期

机译：关于确定命题公式不满足的好的算法
3. DIRECT ALGORITHMS FOR FINDING MINIMAL UNSATISFIABLE SUBSETS IN OVER-CONSTRAINED CSPs [J] . I. SHAH International Journal of Artificial Intelligence Tools: Architectures, Languages, Algorithms . 2011,第1期

机译：在过度约束的CSP中寻找最小不满足子集的直接算法
4. A Branch-and-Bound Algorithm for Extracting Smallest Minimal Unsatisfiable Formulas [C] . Maher Mneimneh, Ines Lynce, Zaher Andraus, International Conference on Theory and Applications of Satisfiability Testing . 2005

机译：用于提取最小最小不可选取的公式的分支和绑定算法
5. Lonicerae Formula and Its Extracts as a Potential Intervention in Atopic Dermatitis for a Clinical Case, Animal Model, and Molecular Targets of Inflammation [D] . Uzun, Serife Elif. 2018

机译：金银花配方及其提取物作为特应性皮炎的一种潜在干预手段，用于临床病例，动物模型和炎症分子靶标
6. Monitoring ratio of carbon to nitrogen (C/N) in wheat and barley leaves by using spectral slope features with branch-and-bound algorithm [O] . Xingang Xu, Guijun Yang, Xiaodong Yang, -1

机译：利用分枝定界算法利用光谱斜率特征监测小麦和大麦叶片碳氮比（C / N）
7. A branch-and-bound algorithm for extracting smallest minimal unsatisfiable formulas [O] . Maher Mneimneh, Inês Lynce, Zaher Andraus, 2005

机译：用于提取最小最小不可满足公式的分支定界算法

A Branch-and-Bound Algorithm for Extracting Smallest Minimal Unsatisfiable Formulas

摘要

著录项

相似文献

相关主题

期刊订阅