一种求解二次分配问题的新方法

系统管理学报196期2010年12月Vol.19No.6Dec.2010JournalofSystems&Management章 :02(1)406一种求解二次分配问题的新方法张惠珍,马良( 理工大学管理学院,200093)摘要二次分配问题(QAP)是一种易于表述却难于求解的组合优化难题。将二次分配问题目标函数中的二次项线性化得到与原问题等价的(混合)整数线性化模型,系统管理学报196期2010年12月Vol.19No.6Dec.2010JournalofSystems&Management章 :02(1)406一种求解二次分配问题的新方法张惠珍,马良( 理工大学管理学院,200093)摘要二次分配问题(QAP)是一种易于表述却难于求解的组合优化难题。将二次分配问题目标函数中的二次项线性化得到与原问题等价的(混合)整数线性化模型,是求解二次分配问题的重要途径,但二次分配问题线性化模型中庞大的变量和约束数,致使利用其求解较大规模的实例仍具有很大。通过松弛原有二次分配问题线性化模型中的约束,得到3个求解规模较小且较松弛的模型,提出了一种求解二次分配问题的新方法,并不仅从理论上证明了该方法的正确性,也从实验的角度说明了该方法较以往方法的优越性。:二次分配问题;线性化;模型;线性松弛号:O22ZHANGHuzhen,MALiang(SchoolofManagement,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China)AbstractQuadraticassignmentproblem(QAP)canbedescribedeasily,butitisoneofthemostdifficultcombinatorialoptimizationproblems.LinearizationoftheQAP,gettingridofthequadratictermsheQAPobjectivefunctionbytransforthemoequivalentlinearones,isanimportsolutionmethodfortheQAP.Theverylargenumberofvariablesandconstrasexisting helinearizationoftheQAP,however,usuallyeanobstacleforefficientlysolvingthemoderateQAPins.hispr,wesofthepreviouslinearproedanewsolutionmethodfortheQaresultofrelaxingtheconstraizationoftheQAP,andgotthreenewimprovedlinearizationsoftheQAP.NotonlythetheoreticalresultstitisfeasibleinsolvingtheQAPbyusingthenewsolutionmethod,butalsotheexperimentalreshowsultsshowthesuperioritiesofthenewlinearizations.Keywords:quadraticassignmentproblem;linearization;formulation;linearrelaxationKoopmans等[1]提出二次分配问题(QuadraticAssignmentProblem,QAP)以来,QAP已成为许多学者竞相关注的热点并被应用于诸多领域。日常生活中,调度问题等都可形式化为二次分配问题另外一些Nhard组合优化问题,分问题和最大团问题等也可以转化为二次分配问[4]。二次分配问题属于经典组合优化难题不存在近似度的多项式时间近似算法(>)[45]。该问题一般可描述为:nn个地点,3n!n矩阵,即F=(fij)∀Rn!n,D=(dij)∀Rn!n,C=cij)∀Rnn其中fijij之间的流量;dij表示地点i和j之间的距离cij表示设施i位于位置j的所需花费。要求给每个设施分配到一个地点,并使得设施分配(或配置)到所有地点的总费用最小:nnn收稿日期20090504修订日期20091201min∃∃fijdp(i)p(j)+∃cip(i)(1)作者简介:张惠珍(197),女,博士后,方向为系统工程与.com#p∀i=1j=1i=1智能优化。:zhzzywz@g是所有分配方案的集合;p(ip(j)分别系统管理学报19卷646qijkl=fikdjl+fkidljikjlbij=fiidjj+cij,则可消除上述模型中的冗余变量,yijklk%2iyijil=0jlyijkj=0i)k得到只有n+2 2nn-12个变量的模型:i和j被分配的地点。过去几十年以二次分配问题的线性化模型为基础,求解二次分配问题的方法取得了很大进[67],但由于二次分配问题的线性化模型中引入大量新变量及其约束条件,致使求解问题的规模变得庞大利用线性化模型有效而快速地求解较大规模二次分配问题仍是可望而不可及。本文以二次分配问题的线性化模型为基础通过松弛其线性模型的约束条件系统管理学报19卷646qijkl=fikdjl+fkidljikjlbij=fiidjj+cij,则可消除上述模型中的冗余变量,yijklk%2iyijil=0jlyijkj=0i)k得到只有n+2 2nn-12个变量的模型:i和j被分配的地点。过去几十年以二次分配问题的线性化模型为基础,求解二次分配问题的方法取得了很大进[67],但由于二次分配问题的线性化模型中引入大量新变量及其约束条件,致使求解问题的规模变得庞大利用线性化模型有效而快速地求解较大规模二次分配问题仍是可望而不可及。本文以二次分配问题的线性化模型为基础通过松弛其线性模型的约束条件提出了一种求解二次分配问题的新方法不仅从理论上说明了该方法的正确性,而且,通过测试QAPLIB中的部分实例,说明了该方法的有效和可行性。1 P问题的Jhsn线性化模型所谓二次分配问题的线性化就是通过引入新的0-1或连续变量yijkl(yijkl=xijxkl,1%i,j,k,l%n)及其相应约束条件[7],将二次分配问题的目标函nnn>∃∃∃qijklyijkl+QAPLII=mini=1j=1k>il)jn n>∃bijxij(10)i=1j=1nij1,2,∋,n=1,j=(11)i=1nij1,2,∋,nn=1,i=(12)j=1i-1>yklij+∃-xij+(13)k=1k=i+12,∋,n,j)l-1nxij+∃yklij+∃-yklij=0(14)l=1l=j+12,∋,n,i>k-1nxij+∃yijkl+∃-=0(15):Lawler线性化模型等[810]。其中,文二次分配问题的线性化模型,是截实践中应用相对较多较广的QAP献10]中至目前在模型即l=1i,j,k=l=j+11,2,∋,n,k>iyijkl(0,j)lk>i,(16)(17)∋,ni,j=1,2,nnnn通过引入新的变量和约束将二次分配问题的目标函数线性化后,求解(混合)线性整数规划的经典min∃∃∃∃fikdjlyijkl+QAPLI=i=1j=1k=1l=1nn算法就可被用于求解二次分配问题的线性化模型,,在求解QAP实例时人们更青睐于所耗费的计算资源少,利用其连续或线性松弛所求解的下界值接近于最优目标函数值的模型。虽然QAPLI的变量和约束数较QAPLI的变量和约束数有所减少,但当所求问题的规模较大时,QAPLII中的变量和,这给利用QAPLII在有限的计算时间内有效而快速地求解较大规模QAP实例造>∃cijxij(2)i=1j=1nij∋,n=1,j=1,2,(3)i=1nij1,2,∋,n=1,i=(4)j=1n>yijkl=1,2,∋,nj,k,l=(5)i=1n>yijkl=1,2,∋,ni,k,l=(6)j=11,2,∋,n1,2,∋,n成一定。yijkl=yklij,xij∀{0,1},i,j,k,l=i,j,k,l=(7)(8)(9)i,j%xijxkj2 求解二次分配问题的新方法以上述QAPLII为基础,通过消除QAPLII中的部分约束条件,本文提出下列3种二次分配问题的线性化模型,并将其定义如下:i,j=1,2,∋,nxij(1%:n),yijil=xijxil=0(1%i,j,l%n,j)l),yijkj==01%i,j,k%n,ik)。如果令式2中目标函数n-1 n n nn n>∃∃∃qijklyijkl>∃bijxij:(x,y)∀22 2n-1)/2ÈQAPLRI=mini=1j=1k>il)ji=1j=1且满足式(11)~14式16)和17)6期647nnnnnijklyijkl+>∃bijxij:(x,y)∀22 2ÈQAPLRI=mni=1j=1k>il)ji=1j=1且满足式11)~13),式(15)~17)nnnnn∀n2+n26期647nnnnnijklyijkl+>∃bijxij:(x,y)∀22 2ÈQAPLRI=mni=1j=1k>il)ji=1j=1且满足式11)~13),式(15)~17)nnnnn∀n2+n2(n-1)2/2RÈQAPLRII=mini=1j=1k>il)ji=1j=1且满足式1112式14)~(17)定理1 QAPLRI,QAPLRI及QAPLRIII分别是二次分配问题的线性化模型。,即QAPLRI(x,y)=QAPLII(x,y)。综上所述,FQALRI=FQAPII。同理可证记QAP,QAPLI,QAPLRI,QA证明FQAPLRII=FQAPLII,FQAPRIII=FQAPII。证毕PLRII及QAPLRIII的可行解域分别为:FQAP,FQALII,FQALRI,FQALRII和FQAPRIII。QAPLI是QAP的线性松弛模型,且FQALII=FQAP,故只须证明FQALRI=FQALII,FQALRII=FQALII,FQALRIII=FQALII首先,由上述可知,QAPLRI,QAPLRI及QAPLRII是QAPLII的松弛模型,则FQALIIFQAPLRI,FQAPIIFQAPRII,FQALIIFQALRIII。算例分析选择二次分配基准问题库QAPLIB中的部分3实例来测试本文方法。实验环境:1.70GHzPentium处理器,512MB内存,操作系统为WinXP,优化软件为Cplex90数据前期处理由70完成。每个实例用不同方法求解的最大时间均4hCPU时间。表1给出了所求问题的特征,及用QAPLII,QAPLRI,QAPLRII和QAPLRIII求解问题的规模。表2给出了所求问题的最优解,用不同方法所求的目标函数值及求解问题时花费的CPU时间。为了更好地说明解的质量,表3给出了每个实Gap值,Gap=(当前最优其次,对于(x,y)∀FQALRI,及1%,k%i<n,1)xijxkl=0,xij=0,由式13)知,i-1n>yklij+ ∃k=1yijkl=0。k=i+1=0,xkl=0,由式14知,(2)1问题特征及规模l-1n>yijkl+∃yijkl=xkl=0Nb.OfconstrasNb.OfvariablesIns.nj=1i,l,k=yijkl=0。j=l+11,2,∋,n,k>iIIRIRIIRIIIChr12a12885631608Chr12c12885631608(3)xijxkl=1,xij=xkl=1yijkl=由式14知,0,Had1212885631608l-1nHad14385038502576>yijkl+∃yijkl=xkl=1Nug14385038502576j=1j=l+1那么,必存在∗∀N\{l,j},使得yjl∗=1,且Chr15a475547553180nChr15b475547553180∃yijkl∗+∃1Esc16a579257923872j=1i,k,l∗=1,2,∋,n,k>iEsc16b579257923872nHad16579257923872xkl∗=1ll。显然xkl=1及∃xkl=1l=1Chr18a184714211052829882985544相 ,则yijkl=1。Chr18b184714211052829882985544,(x,y)∀FQALRI,yijkl由上述=052829882985544xijxl,则(x,y)(),(x,y)∀FQALII。此外,由QAPLRI和QAPLII的目标函数的表述可知:对于任一QAP的可行解(xy),经QAPLRI和QAPLII所求得的目标函数值相Chr20a20726001524011440114407640Chr20b20726001524011440114407640Had2020726001524011440114407640系统管理学报19卷6482问题运行结果SolutionCputime(Sec.)Opt.IIRIRIIRIIIIIRIRIIRIIIChr12a9552955295529552955225.37401.85581.838.48Chr12c111561115611156111561115657.111573.961264.8718.57Had12165216521652165216523173.341438.661145.4614400*Had7242724275614400*5319.1814400*14400*Nug0201036106814400*14400*14400*14400*Chr15a9896989689614400*14400*14400*108.3814400*14400*14400*14400*14400*14400*14400*14400*Chr15b79907990885287107990735.1987.7714400*14400*14400*14400*14400*14400*Esc16a68100707072Esc16b292314292292292Had77437203812+++++Chr18a1109834586348181109814400*14400*14400*999.00Chr18b153435323680153414系统管理学报19卷6482问题运行结果SolutionCputime(Sec.)Opt.IIRIRIIRIIIIIRIRIIRIIIChr12a9552955295529552955225.37401.85581.838.48Chr12c111561115611156111561115657.111573.961264.8718.57Had12165216521652165216523173.341438.661145.4614400*Had7242724275614400*5319.1814400*14400*Nug0201036106814400*14400*14400*14400*Chr15a9896989689614400*14400*14400*108.3814400*14400*14400*14400*14400*14400*14400*14400*Chr15b79907990885287107990735.1987.7714400*14400*14400*14400*14400*14400*Esc16a68100707072Esc16b292314292292292Had77437203812+++++Chr18a1109834586348181109814400*14400*14400*999.00Chr18b153435323680153414400*14400*14400*738.60Had18535857305630++552814400*14400*14400*14400*Chr20a21929798219214400*14400*14400*4381.46Chr20b22988454245814400*14400*14400*14400*3问题解的质量Gap/%Branch&BoundNodesSolutionNodesIIRIRIIRIIIIIRIRIIRIIIIIRIRIIRIIIChr12a0.000.000.000.001Chr12c0.000.000.000.00114495801907488Had120.000.000.006.68109210123001Had142.100.000.5226.50741114001Nug148.9612.7914.3963.761Chr15a2.8249.0954.960.0011106Chr15b0.0025.0225.750.001733017614111Esc16a52.0031.4331.43100.001583909111251Esc16b11.464.791.7999.4712155021111281Had1613.80++++++6.264.9046.011++++++2621743812116001+Chr18a78.7077.740.001136711333+Chr18b56.5758.320.00118118+Had1812.1010.59+++56.4011++1541111281++++++Chr20a77.990.00174174Chr20b74.43+8.6718251+494++Had2060.819551解当前最优下界当前最优解100%。此外表3也给出了用不同方法求解时的分支定界节点总数及达到目标函数值时的分支定界节点数。(混合)整数规划问题中,所求下界的质量不仅可以由所求问题的(混合)整数解反映,而且可由其线性松弛解反映。表4给出了每个实例用不同方法求解的线性松弛解及其所花费的CPU时间。2~表4中,所求问题在4hCPU计算时间内没有得到任何可行解时用−表示;由于计算时间的限制计算过程在未得到最优解前而强行结束,用*−表示。由前述QAPLII,QAPLRI,QAPLPRI和6期6494问题的线性松弛运行结果LinearRelaxationSolutionsCputime(Sec.)IIRIRIIRIIIIIRIRIIRIIIChr12a9552.009090.748689.828593.1320.5123.5219.810.80Chr12c11156.009148.859373.5910042.6934.1223.9622.160.65Had1216211606.191604.59894.00147.4547.6249.012.32Had142666.122646.192649.521300.501164.01464.07476.1011.25Nug14922.87887.97884.570.001329.86410.51448.085.10Chr15a9513.1266期6494问题的线性松弛运行结果LinearRelaxationSolutionsCputime(Sec.)IIRIRIIRIIIIIRIRIIRIIIChr12a9552.009090.748689.828593.1320.5123.5219.810.80Chr12c11156.009148.859373.5910042.6934.1223.9622.160.65Had1216211606.191604.59894.00147.4547.6249.012.32Had142666.122646.192649.521300.501164.01464.07476.1011.25Nug14922.87887.97884.570.001329.86410.51448.085.10Chr15a9513.126479.626090.748621.941308.11243.07236.393.27Chr15b7990.006594.026434.485141.00553.79264.63217.382.45Esc16a48.0048.0048.000.006614.081375.851118.2732.59Esc16b278.00278.00278.000.008733.571769.334537.0223.55Had163560.193537.543537.251530.784496.472498.022479.6434.49Chr18a10758.25+++++7319.16+7670.77+9515.3111133.421948.214981.6214.83Chr18b1534.0014400*14400*14400*104.70Had185036.34+++5033.68+++2144.8814400*9338.589164.86137.80Chr20a2156.0014400*14400*14400*221.32Chr20b2242.9214400*14400*14400*218.58Had202827.0814400*14400*14400*430.23QAPLRII的表述及表1可知,对于同一求解问题,QAPLII,QAPLRI,QAPLRII和QAPLRIII的变量数相同;QAPLRI和QAPLRI,且比QAPLII的约束数少,比QAPLRII根据表~,得出如下结论:QAPLII具有很高的紧性这主要体现在对于较小较易求解的QAP实例,如Chr12a,Chr12c,Had12和Chr15a,由QAPLPII所求实例的混合整数规划及其线性松弛规划的目标函数值即为最优目标函数值且Chr12a,Chr12cChr15b3个实例在第1个分支定界点就求得最优解。相对于QAPLI,模型QAPLR,QAPLRII和QAPLRII比较松弛,这主要表现在:除由QAPLRIII求解的Chr18b的线性松弛目标函数值与其最优混合)整,其余由QAPLRI,QAPLRII和QAPLRIII所求实例的线性松弛目标函数值均不等于其(混合)整数规划最优目标函数值另外从分支定界节点总数及达到目标函数值时的分支定界节点数知,由QAPLRI,QAPLRII和QAPLPRIII所求的实例在某一分支定界点的目标函数值已与最优目标函数值相等但证明该分支漫长的过程,如由QAPLRI所求的Ha21个分支定界点的目标函数值已与最优目标函数值相等但证明该点的解QAPLRI,QAPLRI和QAPLRII,,QAPLRI,QAPLRII和QAPLRII较QAPLI易于计算这导致在相同的计算时间内对于相同的(n6),由QAPLR,QAPLRI和QAPLRIII所求的解优于由QAPLII所求的解24所示。就QAPLRI,QAPLRII和QAPLRII而,QAPLRII较QAPLRI和QAPLRII更易计算对于本文所测计算实例,4hCPU计算时间内,QAPLRIII均为其求得了可行解及最优,结语4本文方法在不改变问题解集的条件下通过松弛原有二次分配问题线性化模型中的部分约束探索了一种求解二次分配问题的新方法。虽然利用QAPLRI,QAPLRII和QAPLRIII的线性松弛所求的下界值较劣于利用QAPLII的线性松弛,,由于QAPLRI,QAPLRI和QAPLRIII的求解规模显著小于QAPLII,,使得其在有限的计算时间内利用以分支定界法为基础的优化软件求解QAP实例时能够遍历的分支定界点,系统管理学报19卷650maticalSociety,1994,16:142.LoolaEM,AbreuNMM,oaventrNettoPO,et系统管理学报19卷650maticalSociety,1994,16:142.LoolaEM,AbreuNMM,oaventrNettoPO,etal.Asurveyforthequadraticassignmentproblem为所求实例求得最优解或较优可行解。本文方法从另一侧面也深刻说明了评价二次分配问题线性化方法的优劣,不应只注重其线性松弛最优目标值接近于所求QAP实例最优解的程度,也应体现在该线性化模型的计算难易度能否在合理的计算时间内求得所求实例的最优解或较优的可行解。易于计算且其线性松弛能够提供较优下界的QAP线性化方法才是理想的选择。[4][J].2007,SahniEuropeanJournal176(2):657690.S,GonzalezT.ofOperationalResearch,comlteaproximaton[5]robems[J].JournaloftheAso tonforComptingMachinery,1976,23(3):555565.ela.Theuadraticassgnmentprobem:theory[6]ton,London,KluwerAcaandalgorithm[M].demicPublishers,1998.致谢感谢葡萄牙里斯本大学理学院对本项提[7]CelaE,BurkardRE,PardalosPM,etal.Thequadraticassignmentproblem[A].P.M.PardalosadDZ.Du,ed.HadookofomiatorialOtimization[C]/KluwerAcademicPublishers,1998,241338.LawlerEL.Thequadraticassignmentproblem[J].Manageme