拉格朗日松弛算法

第七章拉格朗日松弛算法当一个组合优化问题被判定为NP完全或NP难时，解决这个问题的常用方法是构造启发式算法，求尽量接近昀优解的可行解。这些算法包括第二章至第六章的局部搜索算法、禁忌搜索、模拟退火、遗传算法、蚁群优化算法和人工神经网络等等。以极小优化目标函数为例，这些算法给出昀优值的上界，第一章的1.4节给出这些算法的目标值同昀优目标值关系的示意图如下：一步法的目标值改进法的目标值基于数学规划：分支定界启发式，割平面启发式，线性规划松弛再对解可行化，拉格朗日松弛可行化等的目标值，现代优化算法：禁忌搜索，模拟退火，遗传算法，蚁群优化算法，人工神经网络等的目标值其它：如限制解空间，分解法，组合算法等的目标值下界算法：线性规划松弛，拉格朗日松弛等的目标值目标值昀优值评价算法好坏的一个标准是考察它所计算的目标值同昀优目标值的差别。由于组合优化问题的难度，求解昀优值有时是非常困难的。解决这个难点的一个有效方法是通过计算下界，用上界和下界的差来评价算法。拉格朗日(Lagrange)松弛算法就是求解下界的一种方法。由于拉格朗日松弛算法的实现比较简单和有比较好的性质，它不仅可以用来评价算法的效果，同时可以用在其他算法中，以提高算法的效率。拉格朗日松弛算法包含两部分内容：一方面是提供下界，另一方面则演变为拉格朗日松弛启发式算法。本章7.1节介绍一些数学规划松弛的方法，7.2节给出拉格朗日松弛的理论，7.3节进一步讨论拉格朗日松弛的适用模型和更一般的结论，7.4节讨论拉格朗日松弛算法，7.5节给出一个应用案例——能力约束单机排序问题。7.1基于规划论的松弛方法在此仅以整数规划为基础讨论，可在混合整数规划问题中作相应的讨论。整数规划的数学模型为(7.1.1)zcstAxbxZTn1=≥∈+min..,x其中，决策变量x为n维列向量，c为n维列向量，A为m×n矩阵，b为m维列向量；系数c，A和b取整数，表示非负整数集合。Zn+1．线性规划松弛在(7.1.1)中将整数变量约束松弛为实数，就可以得到第七章拉格朗日松弛算法172(7.1.2)zcstAxbxRLPTn=≥∈+min...x称(7.1.2)为(7.1.1)的线性规划松弛。线性规划松弛扩大了整数规划的可行解区域。若记{}SxZAxbn=∈≥+|，{}SxRAxbn'|=∈≥+，则有SS⊆'，于是得到结论：定理7.1.1zzLP≤1。定理7.1.1说明线性规划松弛得到整数规划的一个下界。可以通过单纯形算法或多项式时间的内点算法[1]，求得(7.1.2)的线性规划的昀优解。当S中的一个解满足时，推出为(7.1.1)的昀优解。作为求解整数规划问题启发式算法的一部分，线性规划松弛适用于整数规划问题中决策变量是比较大的整数。对这样的问题，启发式算法的两阶段为：第一阶段将整数规划问题松弛为线性规划问题，求解线性规划问题的昀优解；第二阶段将线性规划的昀优解按四舍五入或类似的原则整数化，同时考虑解的可行。x0LPTzxc=0x02．对偶规划松弛方法线性规划(7.1.2)的对偶形式为(7.1.3)zystAycyRDPTTn=≤∈+max..,bz其中，决策y是一个m维列向量。(7.1.2)和(7.1.3)都为线性规划问题，它们的计算方法相同，且由对偶理论得到。至于采用(7.1.2)或(7.1.3)中哪一个求(7.1.1)的下界，需比较哪一个计算简单。无论如何，单纯形算法和内点算法在实际应用中都可能因为耗时过大而不能满足要求。如在一个循环计算的算法中，每一次循环需要求解一个线性规划问题，当循环的步数较大时，这样无论用单纯形算法还是内点算法都会感到计算时间过多，可能无法满足计算时间的要求。zzDPLP=≤13．代理(surrogate)松弛法当(7.1.1)的约束过多时，代理松弛法是通过一个约束axjbijkKjnikKkk==∑∑∑⎛⎝⎜⎞⎠⎟=≥111替代(7.1.1)中的K个约束Kkbxakkinjjji,,2,1,1L=≥∑=。极端的情况可以用一个约束axjbijimjniim==∑∑∑⎛⎝⎜⎞⎠⎟=≥111松弛约束Axb≥。代理松弛法保证目标函数、整数变量约束不变，且因约束的减少造成计算量的减少。4．拉格朗日松弛方法拉格朗日松弛方法的基本原理是：将造成问题难的约束吸收到目标函数中，并使得目标函数仍保持线性性，使得问题容易求解。产生对它的研究兴趣主要基于下面的原因：第一，一些组合优化问题是NP难，除非P=NP，否则在现有的约束条件下不存在求昀优解的多项式时间算法。但在原有的问题中减少一些约束后，求解问题的难度就大大的减少，7.1基于规划论的松弛算法173使得减少一些约束后的问题在多项式时间内求得昀优解。由此，将这些减少的约束称为难约束。对于线性整数规划问题，将难约束吸收到目标函数后，问题又变的容易求解。这时解的质量完全依赖于吸收到目标函数时所选取的参数。例7.1.1集合覆盖问题(Thesetcoveringproblem)设，所有元素()Aaijmn=×aij∈{,}01，且每一列对应一个费用。表示第j列覆盖第i行。集合覆盖问题是以昀小的费用选择一些列使得这些列覆盖所有的行。它的数学模型为cjnj(,,,=12L)cxnaij=1(7.1.4)zSCjjjn==∑min1(SC)st(7.1.5)aximijjjn..,,,,,=∑≥=1112Lxjj∈={,},,,,.0112L(7.1.6)集合覆盖问题是NP难[2]。若将(7.1.5)松弛，可得优化问题zcxstxjnLRSCjjjniijjnimj()min()..{,},,,,,.λλaxjλ=+−∈=≥===∑∑∑111101120L记dcajjiim=−=∑λ1ij,则松弛后的模型为zdxstxjnLRSCjjjniimj()min..{,},,,,,.λλλ=+∈=≥==∑∑1101120L(7.1.7)(7.1.7)很容易求得昀优解xdjj∗=≤⎧⎨⎩100,,,.若其它昀优值为zdxLRSCjjjniim()λλ=+∗==∑∑11.从松弛和求解的过程中看出：对给定的λ≥0，满足(7.1.5)和(7.1.6)的一个可行解自然满足(7.1.7)的约束，因此，zzLRSCSC()λ≤且)zLRSC(λ是SC问题的一个下界。若(7.1.7)的一个可行解不满足约束(7.1.5)时，即存在i，使可以通过调节得axijjjn=∑11,λi，使其增大而惩罚解的不可行性。于是zLRSC()λ同的差距依赖于zSCλ≥0的选取。还可以看出松弛后的昀优解非常容易得到，只需判别dj的正负号。□第二，实际的计算结果证实拉格朗日松弛方法所给的下界相当不错，且计算时间可以接受。同时，可以进一步利用拉格朗日松弛的基本原理构造基于拉格朗日松弛的启发式算法。由上面四种松弛方法，可以给予松弛一个定义：定义7.6.1问题第七章拉格朗日松弛算法174(RP)zxSzxRRR=∈min()满足下列两条性质时，RP称为整数规划(7.1.1)的一个松弛(relaxation)：(1)可行解区域兼容：;SSR⊆(2)目标函数兼容：cxzxxSR≥∀∈(),其中，表示一个解集合，为实函数。SRzxR()定理7.1.2若RP无可行解，则(7.1.1)也无可行解；若(7.1.1)有可行解，则。zzR1≥证明：当RP无可行解时，由可行解区域兼容性，S=∅。当(7.1.1)可行时，(7.1.1)的昀优解为RP的一个可行解，所以。□zzR1≥7.2拉格朗日松弛理论理论告示我们，如果一个整数规划问题可以在多项式时间内求得昀优解，没有必要用更复杂的算法去求解。当面对一个NP难的整数规划问题时，除非P=NP，构造多项式时间的昀优算法已不可能。本章是在整数规划问题为NP难的前提下讨论它的松弛方法。为了适合拉格朗日松弛方法的讨论，将整数规划问题IP描述为(IP)zcxstAxbBxdxZIPTn=≥≥∈+min..),(()复杂约束简单约束其中，(A,b)为m×(n+1)整数矩阵，(B,d)为l×(n+1)整数矩阵。记IP的可行解区域为SxZAxbBxdn=∈≥≥+{|,}。在IP模型中，Axb≥为复杂约束的名称来自于：如果将该项约束去掉，则IP可以在多项式时间求到昀优解，即假定(7.2.1)()min..,cxstBxdxZTn≥∈+简单约束可在多项式时间内求得昀优解。对给定的，IP对λ的拉格朗日松弛(在不对λ的取值产生混淆时，简称为LR)定义为：λλλλ=(,,,)120LmT≥Axd}(LR)zcxbstBxdxZLRTTn()min()...λλ=+−≥∈+LR的可行解区域记为Sx。ZBxLRn=∈≥+{|定理7.2.1LR同(7.2.1)有相同的复杂性，且若IP的可行解区域非空，则∀≥⇒≤λλ0zzLRIP()。证明：令gxcxbAxTT(,)()λλ=+−,则gxcAxbTTT(,)()λλ=−+λ为x的线性函数。而为常数，又因它们的约束相同，故LR同(7.2.1)的复杂性相同。很明显看出且λTbSSLR⊆7.2拉格朗日松弛理论175∀≥∈⇒+−≤λλ0,()xScxbAxcxTTT。由定理7.1.2得到∀≥⇒≤λλ0zzLRIP()。□定理7.2.1说明拉格朗日松弛是IP的下界，我们的目的是求与昀接近的下界。于是需要求解zIP(LD)zzLDLR=≥max()λλ0。问题LD称为IP的拉格朗日对偶。用下例来理解拉格朗日松弛和对偶等概念。先定义凸集和凸包的概念。定义7.2.1若，满足∀∈xyD,αααxyD+−∈≤≤(),101，则称集合D为一个凸集。对离散点集合QP，它的凸包定义为ii=={|,,}12LConQPPiiiiii(){|,}==≥=∑∑ααα01实数。很容易验证Con(Q)为凸集。例7.2.1假设整数规划问题IPzxxstxxxxxxxIP=−−−≥−−−≥−+≥≥min..72245227212121212120(7.2.2)−≥−∈+xxZ224.的第一个约束为复杂约束，那么拉格朗日松弛后的模型LR为zxstxxlxxlxlxlxZLR()min[()()]..)()()().xλλλλ=−+−−−−−≥−+≥≥−≥−∈+722520122722344121212122(4(7.2.3)问题(7.2.3)可以用图解的方法简单求解。图解形式如示意图7.2.1。01234x11234l1l2l3l4⊙⊙⊙⊙⊙⊙⊙ABCDE(,417117)⊙x2图7.2.1(7.2.3)的图解示意其中，⊙表示整数点，ABCDE分别表示(7.2.3)的可行解集的极点，图中的四条直线分别代表(7.2.3)四个约束取等号时的直线方程。当λ=0时，目标函数的下降方向是(7,2)T，图解(7.2.3)的昀优解为(3,4)T，第七章拉格朗日松弛算法176zLR()02=−9。当λ=12时，目标函数的下降方向是(7.5,1)T，图解(7.2.3)的昀优解为(4,0)T，zLR()1232=−。当λ=1时，目标函数的下降方向是(8,0)T，图解(7.2.3)的昀优解为(4,0)T，zLR()13=−2。由目标函数可知，为目标函数的下降方向。当T)22,7(λλ−+λ在[,变动时，单位化的方向从)0+∞T)532,537(顺时针变化到TT)52,51()565322,56537(lim22−=++−+++∞→λλλλλλλ。于是，只可能在两点(3,4)T和(4,0)T达到昀优解。根据图7.2.1中的方向变化求得目标值。过(3,4)T和(4,0)T两点的直线方程为yx+=416，在图7.2.1中用虚线表示，它的一个垂直方向是T⎟⎟⎠⎞⎜⎜。此时求得满足⎝⎛171,174T)561122,56117(22λλλλλλ++−+++=T⎟⎟⎠⎞⎜⎜，⎝⎛171,174的λ∗=19。当时，昀优解为(3,4)0≤≤∗λλT。当时，昀优解为(4,0)λ∗≤λT。综合得到zLR(),,,.λλλλλ=−+≤≤−−≥⎧⎨⎪⎪⎩⎪⎪2901928819当当(7.2.4)由(7.2.4)解出(7.2.2)的拉格朗日对