[教育]運(yùn)籌學(xué)3.4分枝定界法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

28、 .,,要求分枝到結(jié)點(diǎn)i 的右子結(jié)點(diǎn),針對(duì)所要求解問題的具體特性, 可選取適當(dāng)?shù)奶幚聿呗詠硗瓿煞种?、定界等操? 也可按照問題的具體特點(diǎn)來設(shè)計(jì)一些特定的處理方法.,確定了相應(yīng)的處理方法之后， 就可通過對(duì)一般分枝定界算法進(jìn)行具體化來得到求解具體問題的某個(gè)分枝定界算法 .,下面給出基于線性規(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)目標(biāo)函數(shù)值的上界 .,基于LP松弛的B&B,

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

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

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

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

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

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

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

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

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

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

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

41、 .,令下界 之值等于到目前為止所找到的問題(KP )最好可行解所對(duì)應(yīng)的目標(biāo)函數(shù)值.,給定 和 的值后, 可以使用下列兩個(gè)檢驗(yàn)方法來固定某些變量之取值.,變?cè)シ?1,如果 且

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

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

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

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

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