一種整數(shù)線性乘積規(guī)劃問題的分支定界算法

李敏敏 ,高岳林

(1.北方民族大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,寧夏 銀川 750021;2.寧夏科學(xué)計算與智能信息處理協(xié)同創(chuàng)新中心,寧夏 銀川 750021)

1.引言

整數(shù)規(guī)劃可用于解決眾多領(lǐng)域中的實際問題,如工商管理、工程技術(shù)、金融及社會科學(xué)等.隨著科學(xué)技術(shù)的發(fā)展和決策問題求解的迫切需要,非線性整數(shù)規(guī)劃問題的算法研究已經(jīng)成為運籌學(xué)與最優(yōu)化領(lǐng)域的研究熱點之一.[1-2]求解非線性整數(shù)規(guī)劃問題的確定性方法有割平面法[3]、分解算法[4]、外逼近法[5]、分支定界法[6-10]等.由于整數(shù)規(guī)劃是NP難問題,現(xiàn)有算法僅可以求解某種特殊形式的整數(shù)規(guī)劃問題,且往往存在收斂速度慢、最優(yōu)解效果差、計算復(fù)雜等不足,對于特殊的非線性整數(shù)規(guī)劃問題――整數(shù)線性乘積規(guī)劃問題,至今還沒有一個通用而有效的算法.本文主要考慮以下形式的整數(shù)線性乘積規(guī)劃問題:

這里αj>0,cj ∈Rn,dj ∈R,j=1,···,p.A ∈Rm×n,b ∈Rm,假定+dj ≥ε>0,j=1,···,p.X0為非空有界閉集.

(ILMP)不僅應(yīng)用于金融優(yōu)化[11]、證券投資[12]、微觀經(jīng)濟(jì)學(xué)[13]等金融經(jīng)濟(jì)問題中,而且在VLISI芯片設(shè)計[14]、數(shù)據(jù)挖掘[15]、魯棒優(yōu)化[16]等方面也有涉及.由于(ILMP)問題是一個NP-hard問題[17],且往往存在許多局部最優(yōu)解而不是全局最優(yōu)解,這就使得在理論和計算上存在巨大的挑戰(zhàn).因此,尋找一種有效的算法全局求解(ILMP)問題是十分必要的.

從(ILMP)問題的研究歷程來看,已經(jīng)有許多算法都適用于求解全局(LMP)問題,求解全局(ILMP)問題的算法相對較少,現(xiàn)如今分支定界算法已成為求解這類問題最常用的工具之一.根據(jù)分支定界算法的框架,基于對(ILMP)問題的松弛,在每個節(jié)點求解松弛子問題的下界,得到一個高質(zhì)量的下界對原問題起著至關(guān)重要的作用.SHAO和Ehrgott[18]提出了利用多目標(biāo)線性規(guī)劃和原始對偶條件求解(LMP)問題的全局優(yōu)化算法.對于廣義線性乘積規(guī)劃問題,JIAO[19]利用指數(shù)函數(shù)和對數(shù)函數(shù)的線性逼近,建立了一類廣義線性乘法規(guī)劃的可靠高效算法.SHEN[20]將適當(dāng)刪除技術(shù)與分支定界格式相結(jié)合,提出了求解廣義線性乘法規(guī)劃的一種新的加速方法.針對指數(shù)型線性乘法規(guī)劃問題,LIU和ZHAO[21]在Youness[22]的研究基礎(chǔ)上提出了一個水平集算法.SHEN等人[23]提出了一個完全多項式時間逼近算法.對于約束中具有線性乘積項的問題,Benson[24]提出了一種基于分解的分支定界算法,Kuno[25]提出了一種基于Soland矩形分支定界法最小化多面體上仿射函數(shù)乘積的算法.

非凸(ILMP)問題的困難源于決策變量的非連續(xù)性以及目標(biāo)函數(shù)為線性乘積,松弛過程中需要將目標(biāo)函數(shù)的連乘利用對數(shù)恒等式進(jìn)行轉(zhuǎn)換以及將決策變量松弛為連續(xù)變量,本文給出了求解整數(shù)線性乘積規(guī)劃(ILMP)問題的全局優(yōu)化算法.該算法結(jié)合分支定界操作和區(qū)域縮減技術(shù),通過利用對數(shù)函數(shù)的恒等式,將目標(biāo)函數(shù)等價轉(zhuǎn)化為對數(shù)函數(shù)求和的形式,使用線性松弛技術(shù)將非凸(ILMP)問題轉(zhuǎn)化為線性松弛規(guī)劃問題,并將其嵌入到分支定界操作中.為了加快算法的收斂速度,在分支和定界過程中采用了區(qū)域縮減技術(shù),為當(dāng)前不存在全局最優(yōu)解的區(qū)域提供了理論可能性,可以顯著減少松弛間隙.結(jié)合新的線性化技術(shù)、分支定界操作、區(qū)域縮減技術(shù),本文提出了一種簡化的分支定界區(qū)域縮減算法.最后,數(shù)值實驗結(jié)果表明,該方法能較好地解決所有存在于全局最優(yōu)解中的(ILMP)問題.

本文的組成結(jié)構(gòu)如下: 第一部分提出了整數(shù)線性乘積規(guī)劃問題,并且概述了求解整數(shù)線性乘積規(guī)劃問題的相關(guān)算法.第二部分描述了怎樣將問題(ILMP)轉(zhuǎn)化為一個等價的問題(EILMP(Hk)).第三部分利用對數(shù)函數(shù)的單調(diào)性和凹凸性得到(ILMP)的松弛問題.第四部分將第三部分得到的線性松弛規(guī)劃,以及區(qū)域縮減技術(shù)嵌套在分支定界框架內(nèi),得到線性松弛分支定界算法以求解整數(shù)線性乘積規(guī)劃問題.第五部分通過實例證明算法的有效性和可行性.第六部分得出相關(guān)結(jié)論.

2.等價問題

為了以下敘述的方便,我們首先介紹兩個常用的取整函數(shù),分別是上取整函數(shù)和下取整函數(shù).上取整函數(shù)在數(shù)學(xué)中記作「r?,表示不小于r的整數(shù)中最小的一個;下取整函數(shù)在數(shù)學(xué)中記作「r」,表示不超過r的整數(shù)中最大的一個.即:

本節(jié)將分兩個階段對問題(ILMP)進(jìn)行等價轉(zhuǎn)換.

第一個階段:記問題(ILMP)的可行域為X=X0∩Zn,構(gòu)造包含X的整超矩形H=[l,u]={x|l ≤x ≤u,l,u ∈Zn},其中

這里ai,bi分別是(2.1),(2.2)的最優(yōu)值,當(dāng)i ∈{1,2,···,n}時,

因此,我們得到問題(ILMP)在Hk上的第一個等價問題如下:

第二個階段: 根據(jù)對數(shù)恒等式以及對數(shù)函數(shù)的性質(zhì)可得:

根據(jù)指數(shù)函數(shù)的單調(diào)性,問題(ILMP)可被再次改寫為以下問題:

3.定界技術(shù)

我們將利用對數(shù)函數(shù)fj(y)=ln(yj)的凹凸性給出問題(ILMP)在超矩形上的下界函數(shù)hj(y)為:

定理3.1對于任意的y ∈V k,考慮fj(y)和hj(y)有下列兩條性質(zhì):

1) 函數(shù)hj(y)是函數(shù)fj(y)的凸包,另外fj(y)和hj(y)滿足:

2)fj(y)和hj(y)之間的差值滿足:

其中,?j(y)=fj(y)-hj(y).

2) 記Θj(yj)=?j(y),我們有:

根據(jù)定理3.1,問題(EILMP(Hk))可被松弛為:

注2?k中的點x?也不一定滿足x?∈X0,所以在算法中需要判斷這些解的可行性.

4.分支定界算法及其理論分析

Ⅰ 整超矩形的分支規(guī)則

為了得到原問題(ILMP)的全局最優(yōu)解,提出了整超矩形分支定界算法.在H0被剖分后的子集上求解一系列線性松弛規(guī)劃問題.在分支過程中,需要依據(jù)一定的剖分規(guī)則將初始超矩形H0分成兩個新的子矩形.本文所采用的是標(biāo)準(zhǔn)整超矩形二分方法.考慮任一通過Hk=[lk,uk]所確定的子節(jié)點問題.分支規(guī)則如下所示:

通過以上分支規(guī)則,將矩形區(qū)域Hk剖分成兩個子矩形Hk1和Hk2.

為了方便起見,把H0的任意子整超矩形都記作Hk,記LBk是線性松弛規(guī)劃問題(LRP(Hk))的最優(yōu)值,xk是相對應(yīng)的最優(yōu)解.

Ⅱ 整超矩形的縮減規(guī)則

結(jié)合矩形分支規(guī)則和縮減規(guī)則,設(shè)計了以下求解問題(ILMP)的分支定界算法,步驟如下:

步1 (初始化)

步1.1 構(gòu)造關(guān)于x的初始整超矩形H0=[l0,u0],置可行解集合W=?.

步1.2(初始下界) 求解問題(LRP(H0)),置初始下界L0=min{Fl(x,y):x ∈H0},對應(yīng)最優(yōu)解為(x0,y0).

步1.4 置容忍度ε>0,迭代次數(shù)k=0;超矩形集合Q=?.

步2 (迭代過程)

步2.1(終止條件) 若Uk-Lk<ε,且(xk,yk)是問題(EILMP)的可行解,則迭代終止.輸出問題(EILMP)的全局最優(yōu)解(x?,y?)=(xk,yk),然后將x?代入原問題(ILMP)的目標(biāo)函數(shù)求得最優(yōu)值f(x?).否則令剖分產(chǎn)生的超矩形集合Q=Q∪{H0};轉(zhuǎn)置步2.2.

步2.2(超矩形選擇) 置Hk=min{L(H)|H ∈Q}.

步2.4(超矩形縮減) 運用前面給的整超矩形的縮減規(guī)則,對剖分后的子超矩形進(jìn)行縮減,為了方便起見,把縮減后產(chǎn)生的新的超矩形仍然記為Hkj,(j∈{1,2}).

步2.5(子問題求解)求解問題(LRP(Hkj)),置Lkj=min{Fl(x,y) :x ∈Xk∩Hkj},對應(yīng)最優(yōu)解為(xkj,ykj)(j ∈{1,2}).

步2.7(超矩形刪除) 若L(Hkj)

步2.8(更新上下界)

步2.8.1(更新上界) 置Uk=min{Uk,min{F(x,y): (x,y)∈W}},若Uk=min{F(x,y):(x,y)∈W},則當(dāng)前最優(yōu)解(x?,y?)=argmin{F(x,y) : (x,y)∈W}.其中x?為原問題(ILMP)的最優(yōu)解.

步2.8.2(更新下界) 置Lk=min{L(H):H ∈Q},置k=k+1,轉(zhuǎn)置步2.

證假設(shè)(xk,yk)是問題(LRP(xk,yk))的ε-全局最優(yōu)解,這里yj=+dj,j=1,2,···,p.如果(xk,yk)是(EILMP(xk,yk))的可行解,根據(jù)U和L(Hk)的定義知

定理4.1證畢.

定理4.2假設(shè)(EILMP)問題的可行域是非空的,且矩形的剖分是耗盡的,則以下結(jié)論成立: (EILMP)問題的全局最優(yōu)解將在算法迭代有限步終止時得到.

證因為本文研究的是整數(shù)規(guī)劃問題,故算法迭代在有限步終止,假設(shè)算法是在第k次迭代終止,k ≥0.根據(jù)算法的步1和步2.1得到Uk-Lk ≤ε.由步1和步2.8.1可知,等價問題(EILMP)存在可行解(x?,y?)使得Uk=F(x?,y?),因此有

假設(shè)v是等價問題(EILMP)的全局最優(yōu)值,由下界的計算過程表明

由于(x?,y?)是等價問題(EILMP)的可行解,有

聯(lián)立式(4.3)-(4.5)得

所以,(x?,y?)是等價問題(EILMP)的全局最優(yōu)解.

定理4.2保證了當(dāng)∥l-u∥→0時線性松弛規(guī)劃問題(LRP(Hk))無限地逼近于等價問題(EILMP),說明本文給出的分支定界算法是全局收斂的.

5.數(shù)值實驗

以下給出幾個例子證明本文算法的有效性.本文算法中所有的線性規(guī)劃問題均選用對偶單純形法求解,算法所有測試過程均用MATLAB9.2.0.538062 (R2017a)在Inter(R)Core(TM)i5-8250U,CPU@1.60GHz,4GB內(nèi)存,64位Windows10操作系統(tǒng)的計算機上運行.

算例1[27]

通過本文的算法將算例1轉(zhuǎn)化為以下等價問題(EILMP):

其中H1=[1,1,1,1,1;1,2,1,1,2]T,V1=[18,6,2,10;21,12,8,13]T,圖1中的○1處的矩形為H1,

圖1 分支流程圖

下面構(gòu)造線性規(guī)劃松弛問題(LRP):

解線性規(guī)劃問題(LRP),得出問題在第一個矩形H1上的下界8.9206,在第一個矩形H1上得到上界對應(yīng)的最優(yōu)解x1=[1;2;1;1;1],最優(yōu)值9.1595;再選擇下界對應(yīng)的矩形H1作為下次剖分的矩形,通過本文的剖分規(guī)則得到矩形H11=[1,1,1,1,1;1,1,1,1,2]T,H12=[1,2,1,1,1;1,2,1,1,2]T,圖1中的○2處的矩陣為H11,○4處的矩陣為H12;對H11進(jìn)行縮減,在H11上計算的下界為9.2183,大于當(dāng)前上界9.1595,H11被刪除,此時在圖1中對應(yīng)的位置是○3,對H12進(jìn)行縮減,在H11上計算的下界為9.1595,H12被刪除,這樣超矩形的集合T為空,松弛問題的目標(biāo)值為9.1595,全局最優(yōu)值為9.1595,最優(yōu)解為x1=[1;2;1;1;1],具體迭代過程如圖1.

算例2[21,26-28]

算例3[21]

算例4[21]

算例5[21,26-28]

根據(jù)文[28],我們可知算例5可被改寫為:

算例6

算例1-5的計算結(jié)果如表5.1所示,算法運行過程中的精度為10-4,得到最優(yōu)值f(x?)和最優(yōu)解x?.表5.2表示每個算例使用不同的算法得到的平均迭代次數(shù)(Iteration(次))和平均運行時間(Time(s)).利用文[21,26-28]中的算法和本文算法進(jìn)行比較,從總體看本文算法在5個算例上取得的最優(yōu)值和最優(yōu)解與其他算法的相同,證明了本文算法的有效性.從計算效果看,本文算法在算例1,算例3和算例4中無論是平均迭代次數(shù)還是平均運行時間上均取得了不錯的效果,在算例2中本文算法的運行效果與其他算法相比相差不大.在算例5中本文算法無論是在平均迭代次數(shù)還是平均運行時間方面與其他算法相比較差.從總體看5個算例的數(shù)值結(jié)果證明了我們提出的算法是可行并且有效的.

表5.1 算例1-5利用本文算法產(chǎn)生的數(shù)值結(jié)果

表5.2 算例1-5 利用本文算法產(chǎn)生的數(shù)值結(jié)果

為了進(jìn)一步證明我們的算法是有效的,對算例6進(jìn)行了隨機試驗,計算結(jié)果呈現(xiàn)在表5.3和5.4中,下文也做出了相應(yīng)的說明.

表5.3 算例6利用本文算法產(chǎn)生的數(shù)值結(jié)果

由于目前求解整數(shù)規(guī)劃的分支定界算法較少,本文通過Matlab自帶的求解非線性規(guī)劃的求解器fmincon來對比最優(yōu)值進(jìn)而證明算法的可行性,另外由于求解器無法求解整數(shù)規(guī)劃問題,特在約束條件中加入x(1-x)=0的等式約束,確保求得的解為整數(shù)解.因此使用求解器fmincon和我們的算法對算例6同時進(jìn)行計算,并將結(jié)果置于表5.3和5.4中,表中m表示約束條件的個數(shù),n表示目標(biāo)函數(shù)的維數(shù),p表示目標(biāo)函數(shù)中線性乘積項的個數(shù),在表5.3中,在m和p不變n逐漸增大的情況下,m較小時,迭代次數(shù)與迭代時間明顯增加,m較大時,迭代次數(shù)與迭代時間均無明顯變化;當(dāng)n和p固定,m不斷增加時,迭代次數(shù)與迭代時間均無明顯變化.而且,隨著p的增加,迭代次數(shù)和迭代時間在m和n越小時趨于不變.另外,本文算法求得的最優(yōu)值與求解器fmincon求得的完全相同,故表明我們的算法是有效的.在表5.4中,在m和n不變p逐漸增大的情況下,迭代次數(shù)和迭代時間基本保持不變.

表5.4 算例6利用本文算法產(chǎn)生的數(shù)值結(jié)果

6.結(jié)論

針對一般的整數(shù)線性乘積規(guī)劃問題,本文基于對數(shù)函數(shù)的性質(zhì)和單調(diào)性求解關(guān)于整數(shù)乘積的線性松弛問題.為了加速算法的收斂性,利用對數(shù)函數(shù)的性質(zhì)和單調(diào)性進(jìn)行松弛,以及結(jié)合區(qū)域縮減技術(shù),通過剖分矩形區(qū)域并解決線性子問題,提出的算法最終收斂到原問題(ILMP)的全局最優(yōu)解.在第五節(jié)數(shù)值實驗中,證實了在求解(ILMP)問題時本文算法是有效并且可行的.