一種求解二次分配問題的新方法

系統(tǒng)管理學(xué)報(bào)196期2010年12月Vol.19No.6Dec.2010JournalofSystems&Management章 :02(1)406一種求解二次分配問題的新方法張惠珍,馬良( 理工大學(xué)管理學(xué)院,200093)摘要二次分配問題(QAP)是一種易于表述卻難于求解的組合優(yōu)化難題。將二次分配問題目標(biāo)函數(shù)中的二次項(xiàng)線性化得到與原問題等價(jià)的(混合)整數(shù)線性化模型,系統(tǒng)管理學(xué)報(bào)196期2010年12月Vol.19No.6Dec.2010JournalofSystems&Management章 :02(1)406一種求解二次分配問題的新方法張惠珍,馬良( 理工大學(xué)管理學(xué)院,200093)摘要二次分配問題(QAP)是一種易于表述卻難于求解的組合優(yōu)化難題。將二次分配問題目標(biāo)函數(shù)中的二次項(xiàng)線性化得到與原問題等價(jià)的(混合)整數(shù)線性化模型,是求解二次分配問題的重要途徑,但二次分配問題線性化模型中龐大的變量和約束數(shù),致使利用其求解較大規(guī)模的實(shí)例仍具有很大。通過松弛原有二次分配問題線性化模型中的約束,得到3個(gè)求解規(guī)模較小且較松弛的模型,提出了一種求解二次分配問題的新方法,并不僅從理論上證明了該方法的正確性,也從實(shí)驗(yàn)的角度說明了該方法較以往方法的優(yōu)越性。:二次分配問題;線性化;模型;線性松弛號: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已成為許多學(xué)者競相關(guān)注的熱點(diǎn)并被應(yīng)用于諸多領(lǐng)域。日常生活中,調(diào)度問題等都可形式化為二次分配問題另外一些Nhard組合優(yōu)化問題,分問題和最大團(tuán)問題等也可以轉(zhuǎn)化為二次分配問[4]。二次分配問題屬于經(jīng)典組合優(yōu)化難題不存在近似度的多項(xiàng)式時(shí)間近似算法(>)[45]。該問題一般可描述為:nn個(gè)地點(diǎn),3n!n矩陣,即F=(fij)?Rn!n,D=(dij)?Rn!n,C=cij)?Rnn其中fijij之間的流量;dij表示地點(diǎn)i和j之間的距離cij表示設(shè)施i位于位置j的所需花費(fèi)。要求給每個(gè)設(shè)施分配到一個(gè)地點(diǎn),并使得設(shè)施分配(或配置)到所有地點(diǎn)的總費(fèi)用最小:nnn收稿日期20090504修訂日期20091201min??fijdp(i)p(j)+?cip(i)(1)作者簡介:張惠珍(197),女,博士后,方向?yàn)橄到y(tǒng)工程與.com#p?i=1j=1i=1智能優(yōu)化。:zhzzywz@g是所有分配方案的集合;p(ip(j)分別系統(tǒng)管理學(xué)報(bào)19卷646qijkl=fikdjl+fkidljikjlbij=fiidjj+cij,則可消除上述模型中的冗余變量,yijklk%2iyijil=0jlyijkj=0i)k得到只有n+2 2nn-12個(gè)變量的模型:i和j被分配的地點(diǎn)。過去幾十年以二次分配問題的線性化模型為基礎(chǔ),求解二次分配問題的方法取得了很大進(jìn)[67],但由于二次分配問題的線性化模型中引入大量新變量及其約束條件,致使求解問題的規(guī)模變得龐大利用線性化模型有效而快速地求解較大規(guī)模二次分配問題仍是可望而不可及。本文以二次分配問題的線性化模型為基礎(chǔ)通過松弛其線性模型的約束條件系統(tǒng)管理學(xué)報(bào)19卷646qijkl=fikdjl+fkidljikjlbij=fiidjj+cij,則可消除上述模型中的冗余變量,yijklk%2iyijil=0jlyijkj=0i)k得到只有n+2 2nn-12個(gè)變量的模型:i和j被分配的地點(diǎn)。過去幾十年以二次分配問題的線性化模型為基礎(chǔ),求解二次分配問題的方法取得了很大進(jìn)[67],但由于二次分配問題的線性化模型中引入大量新變量及其約束條件,致使求解問題的規(guī)模變得龐大利用線性化模型有效而快速地求解較大規(guī)模二次分配問題仍是可望而不可及。本文以二次分配問題的線性化模型為基礎(chǔ)通過松弛其線性模型的約束條件提出了一種求解二次分配問題的新方法不僅從理論上說明了該方法的正確性,而且,通過測試QAPLIB中的部分實(shí)例,說明了該方法的有效和可行性。1 P問題的Jhsn線性化模型所謂二次分配問題的線性化就是通過引入新的0-1或連續(xù)變量yijkl(yijkl=xijxkl,1%i,j,k,l%n)及其相應(yīng)約束條件[7],將二次分配問題的目標(biāo)函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]。其中,文二次分配問題的線性化模型,是截實(shí)踐中應(yīng)用相對較多較廣的QAP獻(xiàn)10]中至目前在模型即l=1i,j,k=l=j+11,2,?,n,k>iyijkl(0,j)lk>i,(16)(17)?,ni,j=1,2,nnnn通過引入新的變量和約束將二次分配問題的目標(biāo)函數(shù)線性化后,求解(混合)線性整數(shù)規(guī)劃的經(jīng)典min????fikdjlyijkl+QAPLI=i=1j=1k=1l=1nn算法就可被用于求解二次分配問題的線性化模型,,在求解QAP實(shí)例時(shí)人們更青睞于所耗費(fèi)的計(jì)算資源少,利用其連續(xù)或線性松弛所求解的下界值接近于最優(yōu)目標(biāo)函數(shù)值的模型。雖然QAPLI的變量和約束數(shù)較QAPLI的變量和約束數(shù)有所減少,但當(dāng)所求問題的規(guī)模較大時(shí),QAPLII中的變量和,這給利用QAPLII在有限的計(jì)算時(shí)間內(nèi)有效而快速地求解較大規(guī)模QAP實(shí)例造>?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為基礎(chǔ),通過消除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中目標(biāo)函數(shù)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。算例分析選擇二次分配基準(zhǔn)問題庫QAPLIB中的部分3實(shí)例來測試本文方法。實(shí)驗(yàn)環(huán)境:1.70GHzPentium處理器,512MB內(nèi)存,操作系統(tǒng)為WinXP,優(yōu)化軟件為Cplex90數(shù)據(jù)前期處理由70完成。每個(gè)實(shí)例用不同方法求解的最大時(shí)間均4hCPU時(shí)間。表1給出了所求問題的特征,及用QAPLII,QAPLRI,QAPLRII和QAPLRIII求解問題的規(guī)模。表2給出了所求問題的最優(yōu)解,用不同方法所求的目標(biāo)函數(shù)值及求解問題時(shí)花費(fèi)的CPU時(shí)間。為了更好地說明解的質(zhì)量,表3給出了每個(gè)實(shí)Gap值,Gap=(當(dāng)前最優(yōu)其次,對于(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問題特征及規(guī)模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的目標(biāo)函數(shù)的表述可知:對于任一QAP的可行解(xy),經(jīng)QAPLRI和QAPLII所求得的目標(biāo)函數(shù)值相Chr20a20726001524011440114407640Chr20b20726001524011440114407640Had2020726001524011440114407640系統(tǒng)管理學(xué)報(bào)19卷6482問題運(yùn)行結(jié)果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系統(tǒng)管理學(xué)報(bào)19卷6482問題運(yùn)行結(jié)果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問題解的質(zhì)量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解當(dāng)前最優(yōu)下界當(dāng)前最優(yōu)解100%。此外表3也給出了用不同方法求解時(shí)的分支定界節(jié)點(diǎn)總數(shù)及達(dá)到目標(biāo)函數(shù)值時(shí)的分支定界節(jié)點(diǎn)數(shù)。(混合)整數(shù)規(guī)劃問題中,所求下界的質(zhì)量不僅可以由所求問題的(混合)整數(shù)解反映,而且可由其線性松弛解反映。表4給出了每個(gè)實(shí)例用不同方法求解的線性松弛解及其所花費(fèi)的CPU時(shí)間。2~表4中,所求問題在4hCPU計(jì)算時(shí)間內(nèi)沒有得到任何可行解時(shí)用?表示;由于計(jì)算時(shí)間的限制計(jì)算過程在未得到最優(yōu)解前而強(qiáng)行結(jié)束,用*?表示。由前述QAPLII,QAPLRI,QAPLPRI和6期6494問題的線性松弛運(yùn)行結(jié)果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問題的線性松弛運(yùn)行結(jié)果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的變量數(shù)相同;QAPLRI和QAPLRI,且比QAPLII的約束數(shù)少,比QAPLRII根據(jù)表~,得出如下結(jié)論:QAPLII具有很高的緊性這主要體現(xiàn)在對于較小較易求解的QAP實(shí)例,如Chr12a,Chr12c,Had12和Chr15a,由QAPLPII所求實(shí)例的混合整數(shù)規(guī)劃及其線性松弛規(guī)劃的目標(biāo)函數(shù)值即為最優(yōu)目標(biāo)函數(shù)值且Chr12a,Chr12cChr15b3個(gè)實(shí)例在第1個(gè)分支定界點(diǎn)就求得最優(yōu)解。相對于QAPLI,模型QAPLR,QAPLRII和QAPLRII比較松弛,這主要表現(xiàn)在:除由QAPLRIII求解的Chr18b的線性松弛目標(biāo)函數(shù)值與其最優(yōu)混合)整,其余由QAPLRI,QAPLRII和QAPLRIII所求實(shí)例的線性松弛目標(biāo)函數(shù)值均不等于其(混合)整數(shù)規(guī)劃最優(yōu)目標(biāo)函數(shù)值另外從分支定界節(jié)點(diǎn)總數(shù)及達(dá)到目標(biāo)函數(shù)值時(shí)的分支定界節(jié)點(diǎn)數(shù)知,由QAPLRI,QAPLRII和QAPLPRIII所求的實(shí)例在某一分支定界點(diǎn)的目標(biāo)函數(shù)值已與最優(yōu)目標(biāo)函數(shù)值相等但證明該分支漫長的過程,如由QAPLRI所求的Ha21個(gè)分支定界點(diǎn)的目標(biāo)函數(shù)值已與最優(yōu)目標(biāo)函數(shù)值相等但證明該點(diǎn)的解QAPLRI,QAPLRI和QAPLRII,,QAPLRI,QAPLRII和QAPLRII較QAPLI易于計(jì)算這導(dǎo)致在相同的計(jì)算時(shí)間內(nèi)對于相同的(n6),由QAPLR,QAPLRI和QAPLRIII所求的解優(yōu)于由QAPLII所求的解24所示。就QAPLRI,QAPLRII和QAPLRII而,QAPLRII較QAPLRI和QAPLRII更易計(jì)算對于本文所測計(jì)算實(shí)例,4hCPU計(jì)算時(shí)間內(nèi),QAPLRIII均為其求得了可行解及最優(yōu),結(jié)語4本文方法在不改變問題解集的條件下通過松弛原有二次分配問題線性化模型中的部分約束探索了一種求解二次分配問題的新方法。雖然利用QAPLRI,QAPLRII和QAPLRIII的線性松弛所求的下界值較劣于利用QAPLII的線性松弛,,由于QAPLRI,QAPLRI和QAPLRIII的求解規(guī)模顯著小于QAPLII,,使得其在有限的計(jì)算時(shí)間內(nèi)利用以分支定界法為基礎(chǔ)的優(yōu)化軟件求解QAP實(shí)例時(shí)能夠遍歷的分支定界點(diǎn),系統(tǒng)管理學(xué)報(bào)19卷650maticalSociety,1994,16:142.LoolaEM,AbreuNMM,oaventrNettoPO,et系統(tǒng)管理學(xué)報(bào)19卷650maticalSociety,1994,16:142.LoolaEM,AbreuNMM,oaventrNettoPO,etal.Asurveyforthequadraticassignmentproblem為所求實(shí)例求得最優(yōu)解或較優(yōu)可行解。本文方法從另一側(cè)面也深刻說明了評價(jià)二次分配問題線性化方法的優(yōu)劣,不應(yīng)只注重其線性松弛最優(yōu)目標(biāo)值接近于所求QAP實(shí)例最優(yōu)解的程度,也應(yīng)體現(xiàn)在該線性化模型的計(jì)算難易度能否在合理的計(jì)算時(shí)間內(nèi)求得所求實(shí)例的最優(yōu)解或較優(yōu)的可行解。易于計(jì)算且其線性松弛能夠提供較優(yōu)下界的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.致謝感謝葡萄牙里斯本大學(xué)理學(xué)院對本項(xiàng)提[7]CelaE,BurkardRE,PardalosPM,etal.Thequadraticassignmentproblem[A].P.M.PardalosadDZ.Du,ed.HadookofomiatorialOtimization[C]/KluwerAcademicPublishers,1998,241338.LawlerEL.Thequadraticassignmentproblem[J].Manageme