一種整數線性乘積規劃問題的分支定界算法

李敏敏 ,高岳林

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

1.引言

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

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

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

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

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

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

2.等價問題

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

本節將分兩個階段對問題(ILMP)進行等價轉換.

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

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

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

第二個階段: 根據對數恒等式以及對數函數的性質可得:

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

3.定界技術

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

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

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

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

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

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

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

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

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

Ⅰ 整超矩形的分支規則

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

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

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

Ⅱ 整超矩形的縮減規則

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

步1 (初始化)

步1.1 構造關于x的初始整超矩形H0=[l0,u0],置可行解集合W=?.

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

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

步2 (迭代過程)

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

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

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

步2.5(子問題求解)求解問題(LRP(Hkj)),置Lkj=min{Fl(x,y) :x ∈Xk∩Hkj},對應最優解為(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},則當前最優解(x?,y?)=argmin{F(x,y) : (x,y)∈W}.其中x?為原問題(ILMP)的最優解.

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

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

定理4.1證畢.

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

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

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

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

聯立式(4.3)-(4.5)得

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

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

5.數值實驗

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

算例1[27]

通過本文的算法將算例1轉化為以下等價問題(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 分支流程圖

下面構造線性規劃松弛問題(LRP):

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

算例2[21,26-28]

算例3[21]

算例4[21]

算例5[21,26-28]

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

算例6

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

表5.1 算例1-5利用本文算法產生的數值結果

表5.2 算例1-5 利用本文算法產生的數值結果

為了進一步證明我們的算法是有效的,對算例6進行了隨機試驗,計算結果呈現在表5.3和5.4中,下文也做出了相應的說明.

表5.3 算例6利用本文算法產生的數值結果

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

表5.4 算例6利用本文算法產生的數值結果

6.結論

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