整數(shù)二次規(guī)劃問題的一種新型分支定界算法

劉 霞，高岳林

（北方民族大學(xué) 信息與系統(tǒng)科學(xué)研究所，寧夏 銀川750021）

整數(shù)規(guī)劃問題是帶整數(shù)變量的最優(yōu)化問題，即在受約束于一組等式或不等式約束條件下最大化或最小化一個全部或部分變量為整數(shù)的多元函數(shù)的最優(yōu)化問題［1］.整數(shù)規(guī)劃的應(yīng)用較為廣泛，許多工程技術(shù)、社會科學(xué)、金融以及工商管理等決策問題都可用其描述.隨著科學(xué)技術(shù)的發(fā)展以及現(xiàn)實(shí)中許多決策問題研究的迫切需要，非線性整數(shù)規(guī)劃問題的算法研究已經(jīng)成為運(yùn)籌學(xué)及最優(yōu)化領(lǐng)域的研究熱點(diǎn)之一［2］.通常研究的整數(shù)規(guī)劃問題是線性的，而一般的線性整數(shù)規(guī)劃問題是NP難的，非線性整數(shù)規(guī)劃問題的難度更大.求解非線性整數(shù)規(guī)劃問題的確定性方法有外逼近法［3-4］、割平面法［5-7］、分解算法［8-9］和分支定界法［10-15］等.已知整數(shù)規(guī)劃問題是NP難問題，而現(xiàn)有的算法只能用于求解整數(shù)規(guī)劃問題的某些特殊形式，并且常常具有收斂速度慢、計(jì)算量大、效率差等許多不足.為了尋求一個可以廣泛而有效地求解一般非線性整數(shù)規(guī)劃問題的算法，本文考慮以下特殊的非線性整數(shù)規(guī)劃問題——整數(shù)二次規(guī)劃問題

其中，Q∈Rn×n是對稱矩陣是非空有界集.

1 松弛定界方法

首先構(gòu)造包含原問題（IQP）可行域的整超矩形R.當(dāng)j∈｛1，2，…，n｝時，計(jì)算以下2n個線性規(guī)劃問題

由式（1）得最優(yōu)解h＊j，由式（2）得最優(yōu)解l＊j.令

可得到包含可行域F=D∩Zn的整超矩形

其中，x-=（x-1，x-2，…，x-n）T，ˉx=（ˉx1，ˉx2，…，ˉxn）T是整數(shù)向量.于是原（IQP）問題等價為以下問題（IPQ）′：

下面考慮問題（IQP）′的連續(xù)松弛規(guī)劃問題（QP）：

首先考慮問題（QP）最優(yōu)值下界的估計(jì).設(shè)λmin是矩陣Q的最小特征值，若λmin≥0，則令θ=0，否則令θ=|λmin|+τ，其中τ≥0，令τ=10-7，因此Q+θI半正定.在矩形Rk=｛x∈Rn|x-k≤x≤ˉxk｝?R上，構(gòu)造f（x）在Rk上的一個線性下界函數(shù).由于

因此

其中

定理1 設(shè)ρ（Q+θI）是半正定矩陣Q+θI的譜半徑，則

證明 由式（3）～（5）得

因此，結(jié)論成立.證畢.

于是得到問題（QP）在矩形Rk上的線性松弛規(guī)劃問題

求解問題（LP（Rk））得到其最優(yōu)值，它的最優(yōu)值是問題（QP）在Rk上的全局最優(yōu)值ν（QP）的一個下界，也是原問題（IQP）在Rk上的全局最優(yōu)值的一個有效下界.即

定上界：通過剖分和縮減超矩形過程中不斷地產(chǎn)生原問題（IQP）的可行點(diǎn)來更新上界.

2 超矩形的剖分與縮減

2.1 超矩形的剖分

Step 2 通過x′與xk的連線或連線所在的平面把超矩形Rk剖分為兩個子超矩形其中邊取整剖分為兩部分，則子超矩形Rk1=中的左下頂點(diǎn)和右上頂點(diǎn)分別為

2.2 超矩形的縮減

為方便敘述，把新產(chǎn)生的超矩形仍記為Rk，是原來超矩形的子集.問題（IQP）中的所有線性不等式約束可變形為然后使用文獻(xiàn)［14］中的超矩形縮減算法進(jìn)行縮減.

3 新型分枝定界算法

到第k步迭代時，要剖分的超矩形和問題（IQP）的可行域分別用Rk和F表示，當(dāng)前找到的所有可行點(diǎn)的集合和剪枝后剩下的超矩形的集合分別用W和T表示.問題（LP（Rk））在超矩形Rk上的最優(yōu)解和最優(yōu)值分別用xk和ν（Rk）表示，當(dāng)前全局最優(yōu)解和最優(yōu)值分別用xν∈arg minν和ν=min｛ν（Rk）：Rk∈T｝表示.問題（IQP）的全局最優(yōu)值的一個下界和上界分別用ν和γ表示，ν對應(yīng)的超矩形用Rν表示.

算法描述：

Step 2（終止條件） 若ν=γ，則終止.輸出問題（IQP）的全局最優(yōu)解xγ和全局最優(yōu)值f（xγ）；否則轉(zhuǎn)到step3.

Step 3（選擇規(guī)則） 在T中選擇ν對應(yīng)的超矩形Rk，即ν=ν（Rk）；

Step 4（剖分方法） 若xk∈Zn，則刪除保留最優(yōu)解xk；否則運(yùn)用2.1中的給出的超矩形剖分方法對超矩形Rk進(jìn)行剖分，剖分后的兩個子超矩形為Rk1，Rk2，并且滿足

Step 5（縮減技術(shù)） 運(yùn)用2.2中給出的超矩形縮減技術(shù)縮減剖分后的子超矩形，新的超矩形仍記為Rki，i∈Γ，其中Γ表示縮減后的超矩形的指標(biāo)集；

Step 6（定上界）

Step 8（定下界）

置k←k+1.轉(zhuǎn)到Step 2.

4 數(shù)值實(shí)驗(yàn)

下面采用MATLAB 7.8.0編程，通過大量的數(shù)值實(shí)驗(yàn)對提出的新算法和文獻(xiàn)［14］中的算法進(jìn)行測試，說明該新算法的可行性、有效性以及優(yōu)越性.所有測試均在Intel（R）Core（TM）i5-3570 K，CPU＠3.40 GHz，4.00 GB內(nèi)存，32位操作系統(tǒng)計(jì)算機(jī)上運(yùn)行.

為了使所測試的算例更具有說服力，并便于與文獻(xiàn)［14］進(jìn)行對比，仿照文獻(xiàn)［14］的算例，針對不同階數(shù)和條件數(shù)，在MATLAB中隨機(jī)生成不同性態(tài)的矩陣Q以及目標(biāo)函數(shù)的一次項(xiàng)向量c，約束條件從表5中選取.針對提出的新算法，表1～3分別給出矩陣Q正定、負(fù)定、不定時規(guī)模不同、約束不同和矩陣Q性態(tài)不同的整數(shù)二次規(guī)劃問題的測試結(jié)果，表4給出了矩陣Q的規(guī)模和約束相同但性態(tài)不同時的幾個100維問題的測試結(jié)果.所有表中的“約束序號”均表示該算例的約束條件在表5中所對應(yīng)的序號，“Q性態(tài)”表示矩陣Q的2-范數(shù)條件數(shù)，“時間”列中的“算法1”表示文章提出的新算法，“算法2”表示文獻(xiàn)［14］中的算法，“整數(shù)最優(yōu)值”表示算法終止時目標(biāo)函數(shù)的最優(yōu)值，“近似最優(yōu)值”表示松弛問題的最優(yōu)值.

表1 Q正定時的整數(shù)二次規(guī)劃問題的計(jì)算結(jié)果 Tab.1 Calculation results of integer quadratic programming problems when Q is positive definite

表2 Q負(fù)定時的整數(shù)二次規(guī)劃問題的計(jì)算結(jié)果 Tab.2 Calculation results of integer quadratic programming problems when Q is negative definite

表3 Q不定時的整數(shù)二次規(guī)劃問題的計(jì)算結(jié)果 Tab.3 Calculation results of integer quadratic programming problems when Q is indefinite

表4 性態(tài)不同的整數(shù)二次規(guī)劃問題的計(jì)算結(jié)果 Tab.4 Calculation results of integer quadratic programming problems with different condition

表5［14］ 不同測試算例中使用的約束條件 Tab.5 Constraints be used in different test examples

從表中可以看出，隨著問題規(guī)模、有效約束以及矩陣Q條件數(shù)的增加，問題的求解時間也在增加，復(fù)雜度自然就增加.將提出的新算法和文獻(xiàn)［14］中的算法進(jìn)行比較，發(fā)現(xiàn)針對同等規(guī)模的問題，所提出的新型分支定界算法的計(jì)算時間遠(yuǎn)小于文獻(xiàn)［7］所提出算法的計(jì)算時間，該算法提高了計(jì)算效率.

5 結(jié) 論

本文研究表明，該新型分支定界算法大大縮短了計(jì)算時間，提高了計(jì)算效率，對于中大規(guī)模的整數(shù)二次規(guī)劃問題效果更為明顯.該算法可用來求解不同規(guī)模、不同條件數(shù)的整數(shù)二次規(guī)劃問題，具有廣泛適用性，算法有效快捷.另外，在分支定界方法中，分支變量和分支方向的選取會影響分支定界算法的效率，這將是下一步研究的問題.

［1］孫小玲，李端.整數(shù)規(guī)劃新進(jìn)展［J］.運(yùn)籌學(xué)學(xué)報(bào)，2014，18（1）：39-68.Sun Xiaoling，Li Duan.Recent advances in integer programming［J］.Operations Research Transactions，2014，18（1）：39-68.（in Chinese）

［2］黃紅選，梁治安.全局優(yōu)化引論［M］.北京：清華大學(xué)出版社，2003.

［3］Buchheim C，Trieu L.Quadratic outer approximation for convex integer programming with box constraints［J］.Lecture Notes in Computer Science，2013，7933：224-235.

［4］Fletcher R，Leyffer S.Solving mixed intger nonlinear programs by outer approximation［J］.Mathematical Programming，1994，66（1-3）：327-349.

［5］Westerlund T，Pettersson F.An extended cutting plane method for solving convex MINLP problems［J］.Computer and Chemical Engineering，1995，19：131-136.

［6］Nowak I，Vigerske S.LaGO：a（heuristic）branch and cut algorithm for nonconvex MINLPs［J］.Central European Journal of Operations Research，2008，16（2）：127-138.

［7］Eronena V P，M?kel?a M M，Westerlundb T.Extended cutting plane method for a class of nonsmooth nonconvex MINLP problems［J］.Optimization，2013：796473.

［8］Flippo O E，Rinnoy Kan A H G.A note on benders decomposion in mixed-integer quadratic programming［J］.Operations Research Letters，1990，9（2）：81-83.

［9］Sun X L，Li J L，Luo H Z.Convex relaxation and Lagrangian decomposition for indefinite quadratic integer programming［J］.Optimization，2010，59（5）：627-641.

［10］Thoai N V.Global optimization techniques for solving the general quadratic integer programming problem［J］.Computational Optimization and Applications，1998，10（2）：149-163.

［11］陳志平，郤峰.求解中大規(guī)模復(fù)雜凸二次整數(shù)規(guī)劃問題的新型分枝定界算法［J］.計(jì)算數(shù)學(xué)，2004，26（4）：445-458.Chen Zhiping，Xi Feng.A new branch-and-bound algorithm for solving large complex integer convex quadratic programs［J］.Mathematic Numerica Sinica，2004，26（4）：445-458.（in Chinese）

［12］Gao Y L，Wang Y J，Du X W.A two-level relaxed bound method for a nonlinear class of 0-1 knapsack problems［J］.Intelligent Information，Management Systems and Technologies，2005，3：461-470.

［13］Zhu W X.A provable better branch and bound method for a nonconvex integer quadratic programming problem［J］.Journal of Computer and System Sciences，2005（70）：107-117.

［14］高岳林，魏飛.一類非負(fù)二次整數(shù)規(guī)劃問題的分支定界縮減方法［J］.計(jì)算數(shù)學(xué)，2011，33（3）：233-248.Gao Yuelin，Wei Fei.A branch-and-bound reduced method for a class of non-negative integer quadratic programming problems［J］.Mathematic Numerica Sinica，2011，33（3）：233-248.（in Chinese）

［15］Misener R，F(xiàn)loudas C A.Glo MIQO：global mixedinteger quadratic optimizer［J］.Journal of Global Optimization，2013，57（1）：3-50.