可满足性问题的扩展研究

命题逻辑的可满足性问题（SAT）是计算机科学的重要问题，已得到深入研究。但由于SAT的表达能力有限，近年来可满足性模理论（SMT）作为SAT的扩展成为新的研究热点。SMT是理论谓词的逻辑组合，具有强大的表达能力，它的判定算法已取得了很大进展。另一方面，很多问题不是判定问题，而是要寻找最优解或计算解空间的大小，而问题的约束中含有复杂逻辑关系，需要用SMT语言来描述，从而超出了经典优化和体积计算问题的范围。因此，本项目将SMT从优化和计数两个方向上进行扩展，研究SMT优化/解空间体积计算问题。在现有的自动推理技术的基础上，为这两类扩展问题设计高效的通用算法，使之适用于多种理论及其组合，既能进行精确求解，又可进行快速估算。算法将以SAT求解器作为布尔逻辑部分的推理引擎，与多种经典优化/体积计算方法有效结合，具备理论学习能力，并采用约束求解等技术来提高效率。项目的成功实施将可有效解决很多应用问题。

可满足性模理论（SMT）是对命题逻辑的可满足性问题（SAT）的扩展，它研究多种领域理论的逻辑组合的可满足性。我们将SMT从判定问题扩展为优化问题和解的计数问题。SMT优化问题即广义的带复杂逻辑约束的优化问题。我们将SMT求解的DPLL(T)框架与经典数学规划方法相结合，提出了一个高效而完备的优化算法并实现了工具。在随机实例上的实验表明，我们的工具比将此类问题转换为混合整数规划再用IBM的商业工具CPLEX求解的速度更快。SMT的解的计数问题即计算SMT公式的解空间体积大小。我们对这一问题分别提出了完备算法和近似算法。完备算法可精确计算十维以内的解空间体积，近似算法可以很高的精度估算出高达几十维的解空间体积。此外，我们将约束求解与优化技术应用于组合测试中，在自动生成组合测试用例，组合测试故障定位等问题上都取得了很好的效果。