约束求解与优化技术的结合及方法-DepartmentofComputerand

1约束求解与优化技术的结合及方法季晓慧1),2)黄拙1)张健1)1)(中国科学院软件研究所计算机科学实验室北京100080)2)(中国科学院研究生院北京100049)摘要：由于约束求解与优化技术的互补性，近年来将二者结合是计算机界及运筹学界的研究热点，其中二者在有限域问题上的结合已取得了较大的发展，但在混合域问题上的结合还有待探索，原因之一是优化技术不能对混合域的问题进行很好的表示。本文提出了将混合约束问题转化为混合整数规划问题的方法，该方法将约束求解技术与混合整数规划联系了起来。用约束求解方法及混合整数规划方法共同求解混合约束问题可以令二者相互借鉴，从而促进二者求解技术的进一步发展。本文方法的提出将会为约束求解与优化技术的进一步结合起到推动作用。同时，由混合约束问题转化而来的混合整数规划问题也可作为求解混合整数规划问题的测试问题（Benchmarks）。关键字：约束求解、优化技术、混合约束问题、混合整数规划1前言从传统的角度来看，约束求解与优化技术分属不同的领域。前者属于计算机科学及人工智能领域，而后者则属于数学中的运筹学范畴。但是由于二者在求解技术上的互补性[1]，以及解决实际问题的需要，近年来它们在不断的互相融合。但是二者的结合仅在有限域问题上较多，在混合约束问题及混合整数规划问题上的结合还不多见，原因之一在于二者不能表示和处理同一问题。本文简要的介绍了约束满足问题、优化问题以及它们各自的求解技术及二者间的结合方法。同时提出了用混合整数规划求解混合约束问题的方法，该方法将混合约束问题的成立与否与混合整数规划问题是否有解联系了起来，它的提出会为约束求解与优化技术的进一步结合起到推动作用。同时所得的混合整数规划问题可以作为求解混合整数规划问题的标准测试问题（Benchmarks）。本文第二部分介绍了约束满足问题与优化问题及各自的求解技术；第三部分介绍了二者之间的结合方法；第四部分提出了用混合整数规划求解混合约束问题的方法；最后对全文进行了总结。2约束满足问题与优化问题及求解方法2．1约束满足问题及其求解方法2.1.1约束满足问题约束满足问题（ConstraintSatisfactionProblem简称CSP）[2]是人工智能领域广泛研究的一类问题。它的基本组成元素为：变量（Variable）V，变量的域（Domain）D以及约束（Constraint）C。变量的域D是变量可能取值的集合，变量Vi只能在它的域Di中进行取值；约束C描述了变量V之间必须满足的关系。约束满足问题的一个解是指为各变量在它的域内取到一个值使得所有的约束都成立。一个约束满足问题可2能有一个、多个或没有解。如果一个约束满足问题至少有一个解，那么它就是可满足的（satisfiable）或者说可行的（feasible），否则它就是不可满足的（unsatisfiable）或者不可行的（infeasible）。根据约束满足问题中变量的域D的不同，约束满足问题可以分为：布尔约束满足问题、有限约束满足问题及混合约束问题。1、布尔约束满足问题布尔约束满足问题要求变量只能在0或1上取值，即布尔约束满足问题的域D为{0，1}。它的约束C实际上就是一组命题逻辑公式（formula）。所谓命题逻辑公式是布尔变量与逻辑连接符按照如下的规则形成的组合体[2]：1.布尔变量是公式；2.如果是公式，则也是公式；3.如果和是公式，则*也是公式；4.只有上面四条规则生成的表达式是公式。这里是一元连接符“非”，*可以是任何一个二元连接符，如（与）、（或）、（蕴含）等。在布尔约束满足问题中，每一个命题逻辑公式也可称为布尔约束条件。布尔变量的取值只有“真”和“假”两种，而经由连接符连接而成的布尔约束条件也只能取“真”、“假”两个值。求解布尔约束满足问题的目的就是为该问题中的布尔变量赋值，使得该问题中的每一个布尔约束条件的值为“真”。2、有限约束满足问题有限约束满足问题，顾名思义，就是变量只能在有限域上取值。在有限约束满足问题中，通常不考虑约束的具体形式，而采用列出所有满足该条件的变量取值组合的形式[2]。N皇后问题、鸽笼问题、图着色问题等都属于有限约束满足问题。实际上，布尔约束满足问题可以看作是有限约束满足问题的特例。3、混合约束问题混合约束问题中的变量可以在多个域中取值，比如变量可以取布尔值、可以在有限数值域及无限数值域上取值等。混合约束问题实质上是对布尔约束满足问题的一种扩展。为了清晰地描述它，我们先作如下定义：定义1数值约束我们称形如Exp1ropExp2的约束为数值约束，其中Exp1与Exp2为数学表达式，如2x-yz，rop为一数学上的关系操作符，包括=，，，，及。定义2混合约束条件混合约束条件由布尔变量及数值约束与逻辑连接符组成，它们按照与命题逻辑公式同样的规则形成组合体。例如)4()3(zxyxa。定义3混合约束问题我们称由一个或一组混合约束条件组成的问题为混合约束问题。一个数值约束有“成立”和“不成立”两种情况，分别对应于这个数值约束的值为“真”和“假”，那么混合约束条件的值就如同布尔约束条件的值一样，也只能取“真”或者“假”。从而求解混合约束问题的目的就是为其中的数值和布尔变量赋值，使得该问题中的每个混合约束条件的值为“真”。下面举一个具体的例子说明混合约束问题：例1：feyyyxbyx)2())2()5(()2(222假设yx,的取值范围都为实数，那么容易验证当x=1，y=1，b=“真”，e=“假”，f=“假”时，原混合约束问题是能够成立的或者说可行的。同样可以验证当x=0，y=2，b=“真”，e=“真”，f=“真”时，原混合约束问题也能够成立。但如果要求x的取值范围为“大于2的实数”，y的取值范围仍为整个实数范围，那么上例这个混合约束问题就是不能够成立的，或者说是不可行的。32.1.2约束满足问题的求解方法总的来说，用于求解约束满足问题的方法包括完备算法与不完备算法两种。所谓完备算法是指能够完全确定某约束满足问题是有解的还是无解的算法；而不完备的算法则在未找到解时不能确定该约束满足问题无解。1、完备算法完备算法中最常用的是回溯法[3]。它先为约束满足问题中的部分变量赋值，在这个部分赋值的基础上为其余的变量赋值。如果在这个部分赋值的基础上，下一个待赋值的变量找不到使得约束成立的解，则需要改变这个部分赋值中所赋的值。回溯法常用的两种策略是：回跳（back-jumping）和向前看（look-ahead）[3]。回跳就是在为下一个待赋值的变量找不到解的时候，不直接为刚赋过值的变量赋其它的值，而是经过分析，找到致使下一个变量无解的那个变量，然后为其改变所赋的值。向前看则是指在为下一个变量赋值时，通常先进行约束推导（constraintpropagation）以及选择最合适的变量及变量的值。约束推导是为了减少搜索空间，而选择最合适的变量及变量的值则是为了加快搜索。有关回溯法的具体策略及其它的求解约束满足问题的完备算法，参见文献[3][4]。2、不完备算法求解约束满足问题的算法大多是搜索法，像回溯法就是一种全局搜索算法，即它要搜索遍整个问题空间。因此，当问题空间很大时，这种算法是不可行的。所以人们提出局部搜索法。局部搜索法以损失解的完备性为代价来提高求解效率。著名的局部搜索算法包括：顾钧的算法、贪心搜索过程GSAT、禁忌搜索（TabuSearch）、拟人拟物法等[2]。其它的还包括爬山法、模拟退火等[5]。关于完备算法与不完备算法间的详尽区别及各自的优缺点读者可参见文献[5]。2．2优化问题及其求解方法2.2.1优化问题优化问题是数学领域的重要分支，它研究如何在众多方案中找出最优的一个。优化问题通常可以用下式进行描述：minf(x)s.t.gi(x)0，i=1，2，…mhj(x)=0，j=1，2，…n其中，f(x)称为目标函数，gi(x)和hj(x)称为约束函数。f(x)，gi(x)，gi(x)都是x的线性函数的优化问题，称为线性优化问题；否则称为非线性优化问题。如果要求得到的解为整数或者部分为整数，那么该优化问题就是整数规划问题。2.2.2优化算法求解线性优化问题的最常用算法是单纯形法[6]，它的提出标志着优化问题形成为一个独立的学科[7]。求解非线性优化问题的主要方法包括牛顿法、最小二乘法、乘子法等[7]，这些算法本质上是迭代法，即给定一个初始值和迭代函数，以此初始值为起始，根据迭代函数计算出下一个值，该过程不断继续直到达到某种条件。可见这种方法十分依赖初始值的选取，在初始值选取不好的情况下，该算法有可能找不到4全局最优解，甚至算法可能发散[8]。因此出现了基于区间分析[9]等技术的全局优化算法[10]，基于区间分析的全局优化算法本质上是分支定界法，它初始为每一个变量赋一较大区间，然后对各区间不断进行检验、折半，直到最后每一变量的区间宽度小于一定的值。求解整数规划问题的方法主要是分支定界法、割平面法等[11]。分支定界法和割平面法都是先求解整数规划问题的松弛问题，所谓松弛问题是指对原优化问题不考虑整数限制的问题；在求得松弛问题的解以后，分支定界法根据所得的变量的值，对原问题添加新的约束以形成新的子问题，而割平面法则是根据求解松弛约束的中间过程添加新的约束以形成新的子问题；对新的子问题再按照上述过程不断的求解，直到最后所得的解为整数，或者得出原优化问题没有整数最优解的结论。另外一大类用于求解优化问题的算法为随机算法（StochasticMethods）[12]，包括：随机搜索（RandomSearch）、禁忌搜索（TabuSearch）、模拟退火（SimulatedAnnealing）、演化计算（EvolutionaryComputations）等[12]。目前，优化问题的求解，尤其是非线性全局优化问题及混合整数规划问题的求解仍是运筹学界研究的热点问题。3约束求解与优化技术的结合3．1约束求解与优化技术的结合现状虽然约束求解与优化技术分属于不同的领域，但是二者间的相互影响却由来已久。20世纪50年代就有人尝试用基于逻辑的方法求解优化问题，只是该方法没有像整数规划方法一样得到广泛的应用[1]。70年代出现的隐枚举法则是基于逻辑的方法在求解整数规划问题上的成功应用[1]。随着整数规划求解方法的不断成熟，从20世纪80年代开始有人研究用整数规划方法来求解布尔约束满足问题。这些学者包括Hooker[13,14]，顾钧[15,16]等。约束求解与优化方法的结合包括以下两个方面：1、约束求解与优化技术解同一问题严格地讲，整数的个数是无限的。但在实际应用中，所涉及的整数的个数通常都是有限的。因此，整数规划与有限约束满足问题都需要在有限的变量域内选取合适的值，使得变量间满足特定的约束关系，也就是说，有限约束求解与整数规划求解技术以不同的角度在解同一问题。这样，结合它们各自的优势来解同一问题就是十分自然的。事实上也的确有很多这类研究[17,18,19]，它们采用不同的方式将约束求解与优化技术结合起来。文献[17]采用的结合方式是用两种技术同时求解同一问题，这被称为冗余建模（RedundantModeling），二者的结合体现在求解同一问题的过程中边界信息（BoundInformation）的交换[17]。大多数学者认为，能够将有限约束求解与整数规划技术结合起来是因为二者有共同之处，同时二者又是互补的[1,17,18,19]。二者的共同之处在于，它们求解问题所采用的方法本质上都是搜索法；而互补之处显而易见，就是二者求解问题的角度和优势不同。约束求解的优势在于它剔除掉不可行空间的能力比较强，而整数规划的优势在于它能利用松弛问题尽早的缩小目标函数的范围[17,18,19]。鉴于上述二者的异同，文献[18]在搜索的过程中交替的使用这两种方法以更好的利用二者的优势。首先，它使用约束求解，以尽量多的剔除掉不可行区域；然后，利用优化技术得到更优的条件并把它加入到问题空间中去；如此循环直到满足结束条件。文献[19]提