混合约束问题求解研究

来源 :中国科学院软件研究所 | 被引量 : 0次 | 上传用户:yisheng
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
混合约束问题具有广泛的应用,如分析基于状态的需求规约、生成软件的测试用例、分析并行化的数据相关性问题等等。对于这类问题的求解,目前的许多方法只能求解单独的某一类约束问题,而不能求解混合约束问题。即使有些方法能够求解混合约束问题,它们也是不完全的,即它不能肯定地告诉用户所求解的混合约束问题是否有解。同时,虽然有些方法能够完全地求解混合约束问题,其求解效率也不够理想。 上述问题归根结底是由于非线性数值约束的存在而产生的,因此本论文提出了两种用于求解数值约束的方法。第一种方法将数值约束转化为一种特殊的优化问题;第二种方法将区间分析与数值法结合起来共同求解数值约束。这两种方法的提出使得我们能够完全、高效地求解混合约束问题。本论文还提出了将混合约束问题转化为整数规划问题的方法,该方法的提出促进了约束求解与优化技术的进一步结合。本论文还将约束求解中的消除同构技术应用于全局无约束优化问题的求解,使得求解全局无约束优化问题的效率得到极大的提高,同时进一步促进了约束求解与优化技术的结合。 本论文提出的将区间分析与数值法结合起来共同求解数值约束是基于既可以利用二者的优势又可以克服二者的缺点。区间分析的优点在于具有较高的可靠性,但其缺点在于效率较低;而数值法的优点在于具有较高的求解效率,但其缺点在于它的正确性依赖于初始值的选取。而将二者结合起来就既可以利用区间分析的高可靠性,又可以利用数值法的高效性,从而也克服了区间分析的效率较低而数值法的可靠性不高的缺点。根据此方法,我们开发了相应的原型工具,并进行了大量的实验,实验结果表明,我们的方法能够可靠、高效地求解数值约束。与单独使用区间分析或者数值法的任何一种方法相比,我们的方法都有明显的优势。 约束求解与优化技术分属不同的领域,但由于二者的互补性,将约束求解与优化技术结合起来求解问题会有更好的结果。本文提出的将混合约束问题转化为混合整数规划问题的方法就是对二者结合的一种探索,该方法将混合约束问题的可行性与混合整数规划问题有特定的解对应起来。该方法的提出将进一步促进约束求解与优化技术的结合。 本文提出的应用消除同构求解全局无约束优化问题的方法也是将约束求解与优化技术进行结合的一种探索。该方法通过消除同构减小了无约束优化问题的搜索空间,从而提高了它的求解效率。我们的方法开创了消除同构技术在非线性优化问题上的求解。
其他文献
随着信息技术、现代通信技术和多媒体技术的高速发展,军队指挥系统的数字化、智能化、网络化、可视化已成为必然的发展趋势。东北大学网络与通信中心提出了远程网络可视指挥系
OWL是W3C提出的Web Ontology语言,用于描述Web资源。OWL-Lite是OWL的一个子语言,它包含了OWL大部分的构造符,提供了较强的语义表达能力,同时与OWL的其它子语言相比,其推理具有较低
聚类分析是数据挖掘领域广泛使用的一种技术,可以自动发现隐含在数据集中的分类模式。 本文在充分分析数据挖掘的相关理论与方法的基础上,详细研究了各种有代表性的聚类算法
本文针对Web服务自动集成问题的几个关键技术进行了研究,主要内容包括以下几个方面: 1、设计面向语义Web服务自动集成的目标描述语言GDL4WSAC:主要解决Web服务自动集成问题中
网络和存储技术的迅猛发展,使数据的传播和积累速度不断增长。从海量数据中挖掘其背后隐减的重要信息变得极为重要,数据挖掘和知识发现技术应运而生。数据挖掘是一项应用广泛
随着信息技术,特别是互联网技术的飞速发展,计算机网络已逐渐成为21世纪全球最重要的基础设施。网络所代表的开放式信息系统是现代信息社会的发展趋势,而由于网络的开放性和复杂
随着电子技术和计算机自动控制技术的引入,报警设施的自动化、智能化水平在不断提高。同时,随着高层建筑和大型综合性建筑的增加,使报警系统更加复杂化和立体化,对报警系统的
本文在研究了XML和Web软件系统模型相关技术的基础上,设计了一套基于XML的Web软件系统模型。该模型由XML数据处理模型、Web服务的安全模型以及XML的显示模型三部分组成。XML数
随着信息时代高新技术的飞速发展,灯光效果控制器广泛应用在广告、宣传、舞台装饰等场合,获得了很好的效果。但现有的灯光效果控制器,其显示方式和控制方式单调,无法形成大型
应用偏微分方程处理图像是近年来在图像处理领域兴起的一种新方法。本文对基于PDE模型的图像恢复方法进行了研究。在图像恢复中,噪声的滤除和图像边缘、细节的保护是一个难以