论文部分内容阅读
混合约束问题具有广泛的应用,如分析基于状态的需求规约、生成软件的测试用例、分析并行化的数据相关性问题等等。对于这类问题的求解,目前的许多方法只能求解单独的某一类约束问题,而不能求解混合约束问题。即使有些方法能够求解混合约束问题,它们也是不完全的,即它不能肯定地告诉用户所求解的混合约束问题是否有解。同时,虽然有些方法能够完全地求解混合约束问题,其求解效率也不够理想。
上述问题归根结底是由于非线性数值约束的存在而产生的,因此本论文提出了两种用于求解数值约束的方法。第一种方法将数值约束转化为一种特殊的优化问题;第二种方法将区间分析与数值法结合起来共同求解数值约束。这两种方法的提出使得我们能够完全、高效地求解混合约束问题。本论文还提出了将混合约束问题转化为整数规划问题的方法,该方法的提出促进了约束求解与优化技术的进一步结合。本论文还将约束求解中的消除同构技术应用于全局无约束优化问题的求解,使得求解全局无约束优化问题的效率得到极大的提高,同时进一步促进了约束求解与优化技术的结合。
本论文提出的将区间分析与数值法结合起来共同求解数值约束是基于既可以利用二者的优势又可以克服二者的缺点。区间分析的优点在于具有较高的可靠性,但其缺点在于效率较低;而数值法的优点在于具有较高的求解效率,但其缺点在于它的正确性依赖于初始值的选取。而将二者结合起来就既可以利用区间分析的高可靠性,又可以利用数值法的高效性,从而也克服了区间分析的效率较低而数值法的可靠性不高的缺点。根据此方法,我们开发了相应的原型工具,并进行了大量的实验,实验结果表明,我们的方法能够可靠、高效地求解数值约束。与单独使用区间分析或者数值法的任何一种方法相比,我们的方法都有明显的优势。
约束求解与优化技术分属不同的领域,但由于二者的互补性,将约束求解与优化技术结合起来求解问题会有更好的结果。本文提出的将混合约束问题转化为混合整数规划问题的方法就是对二者结合的一种探索,该方法将混合约束问题的可行性与混合整数规划问题有特定的解对应起来。该方法的提出将进一步促进约束求解与优化技术的结合。
本文提出的应用消除同构求解全局无约束优化问题的方法也是将约束求解与优化技术进行结合的一种探索。该方法通过消除同构减小了无约束优化问题的搜索空间,从而提高了它的求解效率。我们的方法开创了消除同构技术在非线性优化问题上的求解。