混合整數(shù)典范DC規(guī)劃問題的分支定界算法

馬艷利, 強(qiáng) 華, 馮娟婷

(銀川能源學(xué)院 基礎(chǔ)部，寧夏 銀川 750021)

混合整數(shù)典范DC規(guī)劃問題的分支定界算法

馬艷利, 強(qiáng) 華, 馮娟婷

(銀川能源學(xué)院 基礎(chǔ)部，寧夏 銀川 750021)

針對(duì)一類混合整數(shù)典范DC規(guī)劃問題，提出了一個(gè)基于切平面的分支定界縮減方法.該方法用約束條件的切平面將可行域線性化，并使用了二分規(guī)則.數(shù)值結(jié)果表明所提出的算法是可行的,可以求解大規(guī)模問題.

混合整數(shù)；典范DC規(guī)劃；分支定界；切平面

0 引言

混合整數(shù)非線性規(guī)劃問題廣泛存在于機(jī)械、化工、資源管理、生產(chǎn)調(diào)度、軍事等領(lǐng)域.在混合整數(shù)非線性規(guī)劃問題的研究中，確定型算法是將這個(gè)問題分解為相對(duì)容易求解的混合整數(shù)線性規(guī)劃問題.隨著科學(xué)技術(shù)的發(fā)展和實(shí)際中復(fù)雜決策問題求解的迫切需要，非線性整數(shù)規(guī)劃問題的算法研究已經(jīng)成為運(yùn)籌學(xué)與最優(yōu)化領(lǐng)域的研究熱點(diǎn)之一.求解非線性整數(shù)規(guī)劃問題的確定性方法有外逼近法[1-2]、分支定界法[3-7]、割平面法[8]、分解算法[9]等.由于整數(shù)規(guī)劃問題是NP(non-determinstic polymial)問題,現(xiàn)有算法僅可求解某種特殊形式的整數(shù)規(guī)劃問題，且往往存在計(jì)算量大、收斂速度慢、效率差等不足，甚至特殊的非線性整數(shù)規(guī)劃問題——整數(shù)二次規(guī)劃問題,至今還沒有一個(gè)通用而有效的算法.

DC(differences of two convex functions)規(guī)劃問題是一類重要的優(yōu)化問題，任何一個(gè)DC規(guī)劃都可以轉(zhuǎn)換成典范DC規(guī)劃問題，從而求解DC規(guī)劃問題的最優(yōu)解就轉(zhuǎn)變成求解典范DC規(guī)劃問題的最優(yōu)解.在邊際跟蹤算法的基礎(chǔ)上加入二分規(guī)則和取整要求，使得混合整數(shù)規(guī)劃典范規(guī)劃問題轉(zhuǎn)化成整數(shù)典范DC規(guī)劃問題，并用分支定界算法進(jìn)行求解.許多工程問題中會(huì)遇到類似的求解問題，因而研究混合整數(shù)典范DC規(guī)劃問題的全局解具有十分重要的現(xiàn)實(shí)意義.

本文結(jié)構(gòu)：第1節(jié)描述了典范DC規(guī)劃問題及可行域的整超矩形化；第2節(jié)主要是利用切平面將約束函數(shù)線性化的過程，這是本文的主要內(nèi)容之一；第3節(jié)是基于切平面的分支定界算法，這是本文的主要內(nèi)容.

1 典范DC規(guī)劃問題

本文考慮帶有一般約束的混合整數(shù)典范DC規(guī)劃問題：

其中x=(x1,x2,…,xn),c∈Rn,gi(x):Rn→R,I=1,2,3…是凸的非線性函數(shù),g(x)=θ(x)-γ(x)，θ(x)和γ(x)是Rn上的凸的非線性函數(shù).D為非空有界集，決策向量x為非負(fù)整數(shù)向量.

下面介紹典范DC規(guī)劃問題的最優(yōu)性滿足的必要條件.

定義1[10]定義在凸集X∈Rn上的實(shí)值函數(shù)f稱為X上的DC，是指對(duì)于所有x∈X，f能夠表示成f(x)=p(x)-q(x)，其中p(x)，q(x)是X上的凸函數(shù).

定理1[10](最優(yōu)性必要條件)對(duì)于典范DC規(guī)劃，假設(shè)D是有界的，F(xiàn)非空，并且反向約束g(x)≥0是實(shí)質(zhì)的，G={x∈Rn:g(x)≤0},?G表示G的邊界，那么它在D和G的邊界的交集?D∩?G上存在最優(yōu)解.此外，當(dāng)D是多胞形時(shí)，在D的邊界與G的邊界的交集上.

(1)

(2)

R相當(dāng)于一個(gè)大箱子，把可行域F包起來，問題在R上的最優(yōu)解就是F最優(yōu)解.

2 典范DC規(guī)劃約束函數(shù)的線性化

典范DC規(guī)劃的約束函數(shù)是非線性的，利用非線性函數(shù)的切平面近似地代替非線性函數(shù)，使得可行域R線性化，便于可行域的分解.下面介紹具體的方法.

將約束函數(shù)g(x)=θ(x)-γ(x)在R-=[a-,b-]?R=[a,b]上線性化.函數(shù)θ(x)在點(diǎn)x0的切平面為

θ-(x)是θ(x)的切平面，θ(x)是凸的，有θ(x)≥θ-(x)，所以有如下不等式

得到約束函數(shù)的線性下界.

令

則得到典范DC規(guī)劃問題的線性松弛問題DC*：

3 基于切平面的分支定界算法

fori=1,2,…,m

do begin

then停止．問題DC*在Rk上沒有可行解(Rk被刪除)；

forj=1,2,…,n

endif；

enddo

endif；

Enddo

該算法加入二分規(guī)則，將可行區(qū)域按整數(shù)點(diǎn)切分.

下面介紹整超矩形分支定界算法.

假設(shè)迭代到第k步，F(xiàn)表示問題DC*的可行域，W表示當(dāng)前所找到的可行點(diǎn)的集合.

1)(初始化)構(gòu)造包含F(xiàn)的n維超矩形R0=[a0,b0]?Rn，讓W(xué)={a0,b0}∩F；解線性規(guī)劃問題DC*，得到的最優(yōu)值和最優(yōu)解分別記為η,xη，其中xη所在的超矩形記為Rη，η是問題DC*全局最優(yōu)值的一個(gè)下界．

如果xη∈F，讓W(xué)=W∪{xη}，γ=min{f(x):x∈W}；

如果W=φ,那么γ=+∞；如果W≠φ，那么γ=min{f(x):x∈W}，并找一個(gè)當(dāng)前的最優(yōu)解xγ∈argminγ；

讓T={R0}，k=1．

2) (終止規(guī)則)如果η-γ<ε，則停止計(jì)算，輸出問題DC*的全局最優(yōu)解xγ，全局最優(yōu)值f(xγ)；否則轉(zhuǎn)到下一步．

3)(選擇規(guī)則)在T中選擇超矩形Rk，其中Rk是η對(duì)應(yīng)的超矩形，即η=η(Rk).

4) (剖分規(guī)則)

deleteRk=[lk,uk]，保留最優(yōu)解xk；

else 運(yùn)用上面超矩形的剖分方法，把超矩形Rk剖分為兩個(gè)子超矩形Rk1，Rk2，且intRk1∩intRk2=φ;

endif;

5)(縮減技術(shù))對(duì)剖分后的子超矩形進(jìn)行以下縮減，為了方便起見，把縮減后產(chǎn)生的新的超矩形仍然記為Rki,i∈Γ，其中Γ是縮減后的超矩形的指標(biāo)集.

ifak1=bk1

delete，保留最優(yōu)解xk1；

else 運(yùn)用上面超Rk1矩形的縮減技術(shù)，把Rk1進(jìn)行縮減，

ifRk1被刪除

T=T{Rk}，轉(zhuǎn)到3)；

elseT=T{Rk}∪{Rk1}

解線性規(guī)劃松弛問題(CDC1(Rk1))，得到最優(yōu)值記為ηk1，最優(yōu)解記為xk1；

解線性規(guī)劃松弛問題(DC*(Rk2))，得到最優(yōu)值記為ηk2，最優(yōu)解記為xk2；

6)(定上界)

如果W=φ，那么γ=γ；

如果W≠φ，那么γ=min{f(x):x∈W}，當(dāng)前最優(yōu)解xγ∈argminγ．

7)(剪支規(guī)則)

讓T=T{R:η(R)≥γ，R∈T}．

8) (定下界)

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

4 算例

考慮問題：

通過MATLAB數(shù)值試驗(yàn)，得到問題的最優(yōu)解為x1=1,x2=0,x3=-1.

[1] FLETCHER R, LEYFFER S. Solving mixed intger nonlinear programs by outer approximation[J].Mathematical Programming, 1994(66):327-349.

[2] BERGAMINI M L, SCENNA N, AGUIRRE P. An improved piecewise outer-approximation algorithm for the global optimization of MINLP models involving concave and bilinear terms[J]. Computers and Chemical Engineering, 2008(32):477-493.

[3] MATHUR K, SALKIN H, MORITO S. A branch and search algorithm for a class of nonlinear knapsack problems[J]. Operations Research Letters,1983 (2):155-160.

[4] JUAN M , GROSSMANN E .A branch and contract algorithm for problems with concave univariate, bilinear and linear fractional terms[J]. Journal of Global Optimization ,1999,14:217-249.

[5] STUBBS R, MEHROTEA S. Abranch-and-cut method for 0-1 mixed convex programming[J]. Mathematical Programming, 1999,86:512-532.

[6] 陳志平，李乃成，郤峰．解復(fù)雜二次整數(shù)規(guī)劃問題的新型分支定界算法[J]．工程數(shù)學(xué)學(xué)報(bào)，2004,3(21):371-376．

[7] IVO NOWAK, STEFAN VIGERSKE. LaGO: A (heuristic) branch and cut algorithm for nonconvex MINL-Ps[J].CEJOR, 2008(16): 127-138.

[8] WESTERLUND T, PETTERSSONV F. A cutting plane method for solving convex MINLP proplems [J].Comuter and Chemical Engineering, 1995,19(S):131-136.

[9] FLIPPO O, RINNOY K A. A note on benders decomposion in mixed-integer quadratic programming[J].Operations Research Letters,1990 (9):81-83.

[10] 黃紅選，梁治安. 全局優(yōu)化引論[M]. 北京：清華大學(xué)出版社，2003:31-32．

MixedIntegerModelforDCProgrammingProblemofBranchandBoundAlgorithm

MA Yanli, QIANG Hua, FENG Juanting

(DepartmentofBasic，CollegeofEnergyResourcesofYinchuan，Ningxia750021，China)

Based on a class of mixed integer model for DC programming problems, puts forward a new branch and bound method. In this method, the constraint function is used to be linear and we also use binary rules. Numerical results show that the proposed algorithm is feasible and large-scale problems can be solved.

mixed integer; model for DC planning; branch and bound; tangent plane

2017-05-25

銀川能源學(xué)院科研項(xiàng)目資助(2015-KY-Y-29)

馬艷利(1987—)，女，陜西榆林人，銀川能源學(xué)院基礎(chǔ)部教師.

10.3969/j.issn.1007-0834.2017.03.003

O24

A

1007-0834(2017)03-0013-05