[教育]運籌學3.4分枝定界法

1、§ 3.4 分枝定界法,參考文獻,馬仲蕃線性整數(shù)規(guī)劃的數(shù)學基礎(chǔ) 科學出版社，1998陳志平，徐宗本 計算機數(shù)學 科學出版社，2001Nemhauser G.L. & Wolsey L.A. Integer and Combinatorial Optimization

2、 John Wiley & Sons, 1988,思想 : 間接地列舉或檢驗整數(shù)規(guī)劃問題的所有可行解. 有效判別或檢驗準則的制定、適當限制條件的構(gòu)造等 對于該方法的效率影響很大 .,一. 一般分枝定界法,分枝實質(zhì)上是對問題可行解集的劃分或分解 .,考慮線性整數(shù)規(guī)劃問題,分枝可通過劃分描述 :,D

3、ef. 稱 為 的一個劃分, 如果 , 且對 , 有 .,劃分常常是遞歸進行的, 如右圖所示的分枝定界樹.,,,,,,,,,,,Def. 稱結(jié)點 為結(jié)點 的子結(jié)點, 而 稱為

4、 的父結(jié)點.沒有父結(jié)點的結(jié)點稱為根結(jié)點, 沒有子結(jié)點的結(jié)點為葉結(jié)點. 從一個結(jié)點到任一子結(jié)點之連線稱之為一個分枝, 稱由根結(jié)點到某個葉結(jié)點所對應(yīng)的一組分枝為一條路經(jīng) .,,,,,,,,,,以上劃分過程的極限情形就是對可行解集合S中所有元素的枚舉. 因此也將分枝定界樹稱為枚舉樹.,假定 已被劃分為子集合 . 如果可以論證對于某個

5、 沒有必要做進一步的劃分, 則說分枝定界樹可以在對應(yīng)于 的結(jié)點處被剪枝, 或簡稱為 可以被剪枝 .,Th.2 : 若下列三個條件中的任何一個得以滿足, 則分枝定 界樹可以在對應(yīng)于 的結(jié)點處被剪枝 :,(ⅰ) 不可行性 : ;,(ⅱ) 最優(yōu)性 : 已找到 的一個最優(yōu)解 ;,( ⅲ ) 最優(yōu)值比較 : .,實際

6、中, 遇到滿足條件(ⅰ)與(ⅱ)的機會并不多, 常常通過求解 的某個松弛問題或它的弱對偶問題來應(yīng)用條件( ⅲ ) .,1. 若 不可行, 則 也不可行.,2. 的最優(yōu)值不會大于 的最優(yōu)值 .,設(shè) 為 的任一個松弛問題, 即 的可行解集合和目標函數(shù) 滿足: , 且對任意的

7、 ,有 . 因此, 有下列明顯結(jié)論 :,3. 若 的一個最優(yōu)解為 的可行解, 則它也是 的 一個最優(yōu)解 .,由這些結(jié)論和定理2, 可得用于判別可否剪枝的實用條件 .,ⅰ) 不可行 ;,ⅱ) 的一個最優(yōu)解 滿足 且 ;,ⅲ

8、 ) 對( IP )的某個可行解所對應(yīng)的目標函數(shù)值 , 有 .,Th.3 : 如果下列三個條件中的任何一個得以滿足, 則分 枝定界樹可以在對應(yīng)于 的結(jié)點處被剪枝 :,分枝定界法中的定界就泛是指使用任一策略來尋找、并不斷改進下界 (有時還包括某個上界)的過程 .,一般地, 假設(shè)剛剛求解了 的一個松弛問題, 則在分枝運算對應(yīng)的

9、修正、加細步, 首先劃分 , 取 ,然后構(gòu)造集合 的松弛 , 使得 .,基于上述過程的分枝定界法是一個帶有枚舉特點的松弛算法, 故也被稱為隱含枚舉法 .,在下面給出的算法描述中, L表示一系列整數(shù)規(guī)劃的集合, 每個 具有形式 ,其中 , 與L 中每個問題相關(guān)聯(lián)地有

10、一個上界 ..,一般分枝定界算法步驟 :,S 1 (初始化),S 2 (終止檢驗) 如果 , 則使得 的解 即為 原問題的最優(yōu)解, 終止 .,S 5 (劃分) 設(shè) 為 的一個劃分, 將由此產(chǎn)生的新問題 加到L中去, 并令

11、 . 轉(zhuǎn)S 2 .,S 3 (問題選取與松弛) 從L中選取一個問題 , 并隨之將 其從L中刪除. 求解 的某個松弛問題 ,設(shè)該松弛問 題的最優(yōu)值為 , 并設(shè) 為其一個最優(yōu)解(若存在的話) .,二. 使用線性規(guī)劃松弛的分枝定界算法,考慮將使用線性規(guī)劃松弛的分枝定界算法用于求解如下的整數(shù)規(guī)劃問題 :,在初始松弛中, 由

12、 來代替. 而在以后每個松弛問題中, 總?cè)?.,1.剪枝準則,假設(shè)在分枝定界樹中結(jié)點i處的線性規(guī)劃松弛為,如果 存在最優(yōu)解, 記所找到的最優(yōu)解為 , 則常用的剪枝條件為,這里 為( IP )的某個已知可行解對應(yīng)的目標函數(shù)值. 進而, 對于某個給定的允許誤差界 , 還可以使用弱的條件

13、 來代替該條件 .,4. 利用未被剪枝的結(jié)點之間的某種優(yōu)勢關(guān)系 .,2. 分枝方法,分枝可通過增加線性約束來完成 .,不妨設(shè)現(xiàn)處于分枝定界樹的根節(jié)點處, 則一個顯然的方法是取 ,,其中,關(guān)于 之選取, 有: 如果 為松弛問題,的最優(yōu)解, 則應(yīng)選取 使得 .,這一點

14、將使得 , 從而對于 有可能得到,實際中, 僅選取非常特殊的 , 常見的有 :,1 ) 變元二分法,這時對某個 , 有 .,如果 且 , 則 對所產(chǎn)生的松弛問題不可行.,而如果 , 則左邊的分枝為 , 而右邊的分枝為

15、 .,優(yōu)點 : 只需對現(xiàn)有的線性規(guī)劃松弛問題加上簡單的上、下 界約束即可實現(xiàn) .,2 ) 基于廣義上界約束的二分法,若原問題對某個 含有廣義上界約束 ,,則可通過分別加上約束 和 來定義分枝 .,這里 為 的一個非空子集 .,一個合理的準則是選取 , 使得 與 中所含元素之

16、個數(shù)大致相等 .,若松弛問題的最優(yōu)解 使 , 則 對將生成的兩個松弛問題均不可行 .,,3 ) 基于有界變量法,除非 之值比較小, 否則該法并不實用 .,假設(shè) 有界, 即 , 則可通過分別考慮 的每個允許整數(shù)值來定義分枝.,以下通常假定分枝是由變元二分法來確定的 .,Th.4 : 設(shè) 有界,

17、 并假設(shè)在每個需要分枝 的結(jié)點i處均選取形如 的二分法, 這里 取非整數(shù)值. 則基于變元二分法所產(chǎn)生的分 枝定界數(shù)有限. 特別是, 若 ,則分 枝定界樹之任一條路徑不可能包含多于 個分枝 或條邊 .,Proof:,在某結(jié)點處, 一旦

18、對某個 加上約束,從根節(jié)點起, 穿過該結(jié)點到一個葉結(jié)點的任一條路徑上,在此節(jié)點以后所能出現(xiàn)的其它約束只能是 :,A . 對某個 ,有,B . 對某個 ,有,包含 的約束的最大數(shù)目將為下列情況 :,a ) 對所有

19、 , 加有約束,b ) 對所有 , 均相應(yīng)有約束,c ) 對所有 , 有,d ) 對所有 , 有,對以上情況中任一個, 需要對 加上 個約束 .,在任何路徑上邊的總數(shù)不超過 .,﹟,當P無界時, 可通過利用Th4、Minkowski Th及整數(shù)規(guī)劃問

20、題最優(yōu)解的有界性等來保證分枝定界樹的有界性 .,推論(收斂性) : 分枝定界法必在有限次迭代(循環(huán))后終止,即 它有有限步收斂性.,以問題大小的指數(shù)為界的步數(shù)內(nèi),,,該定理表明, 所得到的界值(對應(yīng)于松弛問題的質(zhì)量)是影響一個分枝定界算法的主要因素 .,Th.5 : 帶有約束集 的分枝定界樹之結(jié)點t滿足 ,

21、則結(jié)點t不可能被剪枝 .,3. 結(jié)點選取方法,兩類選擇方式 : 一是某種先驗的或固定的規(guī)則,二是自適應(yīng)的或稱可調(diào)節(jié)的規(guī)則,先驗規(guī)則,深度優(yōu)先搜索加返回(depth-first search plus backtracking)法 或稱為后進先出(last in, first out, 簡記為LIFO)法則,若當前所考慮的結(jié)點未被剪掉, 則下一個將考慮的結(jié)點是它的(兩個)子結(jié)點中的一個.,主要優(yōu)點 :,⑴ 可減小保存中間樹信

22、息所需的存儲量;,⑵ 易于實現(xiàn),對偶單純形法,⑶ 可較快找到一個可行解及一個較好的下界 .,廣度優(yōu)先搜索( breadth-first search)法,定義分枝定界樹中一個結(jié)點的層次(level)為在連接該結(jié)點與根結(jié)點的唯一路徑中所含邊的數(shù)目.,在考察下一個更深層次的任何節(jié)點之前, 先考慮處于某一個給定層次上的所有結(jié)點 .,,,,自適應(yīng)性規(guī)則,最好上界法,快速改進法,最佳估計法,選取極大化 的 .,選取極大

23、化 的 , 這里 為 的一個估計 .,依準則 來選取結(jié)點i .,有助于盡快找到滿足 的一個可行解 .,4. 分枝變量選擇方法,限于指標集 進行討論 .,依據(jù)某些用戶事先指定的、變量之間的某種優(yōu)先次序, 保證對重要的變量首先進行分枝 .,整數(shù)變量的重要性

24、或優(yōu)先次序?？筛鶕?jù)以下某個或某幾個準則來確定:,1. 它代表了模型中的一個重要決策 ;,2. 與其它變量相比, 它在目標函數(shù)中的效益系數(shù)值很大 ;,3. 按用戶的經(jīng)驗, 它的值是極重要的 .,另兩個簡單而常用的選擇分枝變量的方法 :,4. 選擇線性規(guī)劃解中分量值最大的整數(shù)變量 ;,5. 任意選取, 如先取 中序號最小(大)的變量等 .,也可使用一些復(fù)雜的、自適應(yīng)性方法來選取分枝變量.,降值法(degradations),試圖估計

25、由要求變量 取整值所能引起的上界估計 的下降量.,假設(shè) , 則通過對 進行分枝, 估計出對左子結(jié)點的下降量 , 和對右子節(jié)點的下降量 , 系數(shù) 之值可以作為算法輸入的一部分事先給定, 也可在迭代過程中用某種方法來估計 .,罰值法(pena

26、lties),采用更精細的計算確定系數(shù) 之值, 并有此產(chǎn)生對 的下降量的一個下界估計 .,在給定或估計出對所有 之值 后, 通常采用下面的準則來選取分枝變量 :,7. 選取使 達到極值的某個j 對應(yīng)之 .,6. 選取使 取到最大的某個j

27、對應(yīng)之 .,基本思想 : 其較小下降值為最大的變量對于達到整值解要求來說是最重要的, 當簡單地取 時, 準則6就變?yōu)槌Ｓ玫淖畲笳麛?shù)不可行性(maximum integer infeasibility)法則 .,假設(shè)對每個變量下降值大小的估計是相互獨立的, 則當 時, 有

28、 .,,要求分枝到結(jié)點i 的右子結(jié)點,針對所要求解問題的具體特性, 可選取適當?shù)奶幚聿呗詠硗瓿煞种?、定界等操? 也可按照問題的具體特點來設(shè)計一些特定的處理方法.,確定了相應(yīng)的處理方法之后， 就可通過對一般分枝定界算法進行具體化來得到求解具體問題的某個分枝定界算法 .,下面給出基于線性規(guī)劃松弛的具體分枝定界算法:,S 1 用單純形法求解原整數(shù)規(guī)劃問題(IP )之線性規(guī)劃松弛問 題

29、 .,a ) 若 無可行解或無最大值, 則停止. (IP )亦無可行解或 最大值 ;,b ) 若 有最優(yōu)解, 并符合(IP )的整值條件, 則停止. 該最優(yōu) 解亦是原問題(IP )的最優(yōu)解 ;,c ) 若 有最優(yōu)解, 但不符合問題(IP )的整值條件, 則將 的最優(yōu)值取為(IP )最優(yōu)目標函數(shù)值的上界 .,基于LP松弛的B&B,

30、S 3 置 .,S 4 從L中剪掉所有其上界值小于 的分枝. 若 , 則停止, 便是(IP )的最優(yōu)解. 否則轉(zhuǎn)S 5 .,S 5 依最好上界法從L中選取一個具有最大上屆的子問題, 記 作 , 并令 .,S 6 對于 , 放棄變量的整值性要求后得其線性規(guī)劃

31、松弛問 題 , 用單純形方法求解 .,S 2 用某種啟發(fā)式方法或觀察法來找到問題(IP )的一個整數(shù)可 行解(如可取 進行試探), 記其為 ,將其對應(yīng) 的目標函數(shù)值作為(IP )最優(yōu)值的一個下界 .,S 9 若 的最優(yōu)解 也是 的可行解, 則轉(zhuǎn)S 11, 否則進行

32、 S 10 .,S 10 在 的最優(yōu)解中按整數(shù)變量的某種優(yōu)先次序選取一個 不符合整值要求的變量 , 依變元二分法分別加上約束 條件“ ”和“ ”, 將 分解為兩個子問題 與 , 將它們加入到L中去. 轉(zhuǎn)S 5 .,S 11 若

33、 的最優(yōu)值 大于 , 則令 , 轉(zhuǎn)S 4, 否 則, 即 , 則直接轉(zhuǎn)S 4 .,S 7 若 無可行解, 則轉(zhuǎn)S 4, 否則進行S 8 .,S 8 若 的最大值不超過 , 則轉(zhuǎn)S 4, 否則進行S 9 .,關(guān)于分枝定界法實際應(yīng)用的幾點說明 :,1. 應(yīng)通過對模型的初步分析與預(yù)處理來對整數(shù)變量規(guī)定

34、貼切 的、緊的上、下界限制 . 同時, 確定整數(shù)變量之間的優(yōu)先 順序 .,2. 選取適當?shù)某跏伎尚薪饣蛳陆?, 并對上、下界 、 作及 時、有效的修正 .,3. 實際中算法常常是在達到最優(yōu)性之前就停止. 一個實用的終止準則是當 小于事先給定的誤差 界時終止 .,三. 0—1 背包問題的分枝—定界算法,考慮下列0—1 背包問題,不失一般性,假設(shè)對所有的

35、 .,先來考慮問題(KP )之線性規(guī)劃松弛問題的有效求解與原問題的簡化.,注意到, 如果變量之排序滿足 ,則線性規(guī)劃松弛的一個最優(yōu)解為,這里的r使得 , 而 .,因此, 這個解本質(zhì)上可由r , 或更確定的

36、, 由 來描述.,現(xiàn)給出一個可在 時間內(nèi)求解線性規(guī)劃松弛的算法 .,線性規(guī)劃松弛的求解算法,則算法可描述為 :,令 和 分別表示其值固定在1和0的變量的集合, 表示自由變量的集合. 給定一個候選值 , 令,定義 .,S 1 令

37、 .,S 2 取 為 的中位數(shù)(median) .,S 3 按下列規(guī)則構(gòu)造集合 , 并計算 和 .,ⅰ) 若 , 則令 . 轉(zhuǎn)S 2 ;,ⅱ)

38、 若 , 則令 , , 轉(zhuǎn)S 2 ;,ⅲ ) 否則, 即 , 若 或 , 則可以立即得到一個最優(yōu)整值解而停止. 否則, 以任意次序選

39、取 之元素, 若 , 找出使得 , 的q, 取 , , 且 , 停止 .,該算法終止時給出線性規(guī)劃松弛這樣一個最優(yōu)解:,每次迭代中

40、 的值至少減半,∵,一旦 和 的值被確定, 則可使用下列貪婪啟發(fā)式方法來找到問題(KP )的一個可行解 .,∴ 總運行時間 .,原始啟發(fā)式算法,對上述啟發(fā)式算法的一個明顯改進 :,S 1,S 2,S 3,對 的元素進行排序, 使得

41、 .,令下界 之值等于到目前為止所找到的問題(KP )最好可行解所對應(yīng)的目標函數(shù)值.,給定 和 的值后, 可以使用下列兩個檢驗方法來固定某些變量之取值.,變元消去法 1,如果 且

42、 , 則 .,如果 且 , 則 .,如果 且加上條件 , 則新的線性規(guī)劃松弛為,這里 , 由此得到下列檢驗方法 .,變元消去法 2,變元消去法 1的有效性,變元消去法 2優(yōu)于變元消去法 1,可被固定為1

43、,對于 , 可給出類似的方法來固定 .,且只有當 時等式才成立 .,在所有的消去檢驗均執(zhí)行完了之后所剩余的問題稱原問題的簡化問題, 簡化問題具有與原問題相同的 .,分枝及定界方法,分枝的次序按變量就固定為 , 且每個變量先被置為1

44、, 然后置為0.,結(jié)點t可完全由層數(shù)k和一個滿足 的集合 來限定,假設(shè)問題(KP )已是一個簡化問題, 同時, 變量現(xiàn)已排序并滿足 .,,上界,t 對應(yīng)于可行解的一個非空集合,即為該集合中所有解所對應(yīng)最優(yōu)值的一個下界,剪掉,剪枝,,,,,若該結(jié)點未能按以上方式被剪枝, 則有三種情況 :,ⅱ) . 則通過令

45、 , 而對 取 來得到結(jié)點t的一個最優(yōu)解. 令 并按最優(yōu)性準則剪掉結(jié)點t .,ⅰ) . 若 , 則按 進行分枝; 若 , 則結(jié)點t的一個最優(yōu)解為 . 令 且依最優(yōu)性準則剪掉結(jié)點t.,ⅲ )

46、. 則按不可行性準則剪掉置 的結(jié)點, 并按 進行分枝.,設(shè) ,且 , 則從結(jié)點t的返回可分為下列兩種情況 .,情形 1 : , 即上一次分枝為 , 則返回到層次 并令 .