通信網(wǎng)理論基礎(chǔ)：09-對偶與整數(shù)規(guī)劃

1、通信網(wǎng)絡(luò)理論基礎(chǔ)Part 9: 對偶與整數(shù)規(guī)劃對偶與整數(shù)規(guī)劃2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)2 / 701234對偶理論對偶問題示例對偶單純形算法簡介整數(shù)規(guī)劃的求解方法5小結(jié)拉格朗日乘子法2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)3 / 70如何求解該問題？拉格朗日乘子法的思想：松弛原問題的約束，得到一個無約束問題；引入懲罰因子p，對違背約束的解進行懲罰；只要選擇合適的p，無約束問題的解與原問題一致。LP標準型的對偶(1/2)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)4 / 70松弛掉等式約束可得：懲罰因子的個數(shù)為m。LP標準型的對偶(2/2)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)5 / 70LP標準型的對偶(dual)問題。

2、關(guān)于對偶的第一個印象2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)6 / 70對于LP問題，可以按照拉格朗日乘子法求解其“估值”。求解合適的Lagrange乘子（懲罰因子）等價于求解一個LP問題：原問題（主問題）的對偶問題。Well，至少對標準型，是這樣。更一般的LP問題還是這樣嗎？我們用一個例子來說明。對于更一般的LP問題，其對偶問題是什么樣子？例子：一般的LP(1/4)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)7 / 70除了符號約束之外，每個約束都引入一個懲罰因子，并松弛到目標函數(shù)中。在該松弛問題中，為了體現(xiàn)“懲罰”的含義，必有：例子：一般的LP(2/4)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)8 / 70為了保證最小化La

3、grange函數(shù)有意義，必有：每個主變量都對應(yīng)一個“對偶約束”。例子：一般的LP(3/4)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)9 / 70由于對偶約束與對應(yīng)的主變量“同符號”，其最小值為0。例子：一般的LP(4/4)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)10 / 70主問題對偶問題總結(jié)上述推導(dǎo)，可得：關(guān)于對偶的第二個印象2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)11 / 70主問題minimizemaximize對偶問題約束變量變量約束任給一個LP問題，都可按照上述規(guī)則寫出其對偶問題。真正需要記住的是“懲罰”以及拉格朗日函數(shù)的概念，而不是這些規(guī)則。另一個例子(1/4)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)12 / 70應(yīng)用“懲

4、罰”的概念推導(dǎo)下面最大化問題的對偶問題。另一個例子(2/4)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)13 / 70應(yīng)用“懲罰”的概念推導(dǎo)下面最大化問題的對偶問題。對偶約束和主變量符號相反。另一個例子(3/4)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)14 / 70對偶約束與對應(yīng)的主變量“符號相反”，其最大值為0。另一個例子(4/4)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)15 / 70主問題對偶問題總結(jié)上述推導(dǎo)，可得：有人看出這個例子與上一個例子的關(guān)系了嗎？該例中，主問題是上例中的對偶問題。該例中，對偶問題是上例中的主問題。關(guān)于對偶的第三個印象2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)16 / 70對偶問題的對偶，是主問題。主問題與對偶

5、問題是一一對應(yīng)的。主問題可以推出其對偶問題。對偶問題也可以推出其對應(yīng)的主問題。對偶問題可以看作是主問題的最佳估值問題，那么，這種估值準確嗎？讓我們來討論對偶理論中最深刻的結(jié)論：對偶定理。弱對偶定理2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)17 / 70定理：weak duality theorem主問題對偶問題推導(dǎo)對偶問題的過程中，我們知道：對拉格朗日函數(shù)求最小值(松弛問題)得到的一定是主問題目標函數(shù)值的下界；對偶問題的目標函數(shù)就是松弛問題的目標函數(shù)。故有：兩個推論2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)18 / 70推論1：Let x and p be feasible solutions to the prim

6、al and the dual, respectively, and suppose that pb=cx. Then, x and p are optimal solutions to the primal and the dual, respectively.推論2：強對偶定理(1/2)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)19 / 70假定用單純形法求解主問題，得到最佳解x和最佳基B，則：主問題對偶問題p為對偶可行解。由弱對偶定理的推論2可知，p是對偶最佳解。Reduced Cost，還記得嗎？強對偶定理(2/2)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)20 / 70If a linear program

7、ming problem has an optimal solution, so does its dual, and the respective optimal costs are equal.定理：strong duality theorem主問題對偶問題若標準型主問題存在最佳解，則單純形法一定可以求出。求出了主最佳解，則對偶最佳解也被求出了。因此，有：任一LP問題都可以轉(zhuǎn)化為標準型。關(guān)于對偶的第四個印象2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)21 / 70主問題與對偶問題不僅一一對應(yīng)，而且在下述意義下是等價的：二者的最佳目標值是一致的：估值是精確的。求解主問題的同時，對偶問題的解也被求出了。那么

8、，兩個問題的解的取值有什么關(guān)系嗎？一個重要的結(jié)論：互補松弛定理?；パa松弛定理(1/2)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)22 / 70定理：complementary slackness證明：互補松弛定理(2/2)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)23 / 70證明：弱對偶定理，記得嗎？充要條件得證。關(guān)于對偶的第五個印象2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)24 / 70主問題與對偶問題不僅求解過程是一致的（求解前者的同時也求解了后者），而且求出的解具有密切關(guān)系：若主最佳解非零，則對應(yīng)的對偶約束必取等號。若對偶最佳解非零，則對應(yīng)的主約束必取等號。對偶與整數(shù)規(guī)劃2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)25 / 70123

9、4對偶理論對偶問題示例對偶單純形算法簡介整數(shù)規(guī)劃的求解方法5小結(jié)最短路的對偶(1/2)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)26 / 70最短路的對偶(2/2)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)27 / 70繩球模型2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)28 / 70怎樣理解最大化距離標記？繩球模型。想象隨意放在桌上的一堆繩和球。球頂點；繩邊。繩的長度=邊的權(quán)重。一手拿s，一手拿i，拉伸到不能再拉為止。最優(yōu)條件：RC非負。Bellman-Ford算法2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)29 / 70Ring a bell？Yes, its Bellman-Ford algorithm!事實上，上述方程成為Bellman

10、方程。繩球模型：先將s上的繩子拉直，然后將s鄰接點的繩子拉直；一直進行下去，直至所有點i到s的繩子都被拉直。對偶的用途：設(shè)計新算法2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)30 / 70主問題與對偶問題是等價的。因此求解對偶問題的算法同樣可以求解主問題。Bellman-Ford算法求解的其實不是最短路，而是距離標記（對偶變量）。最大流的對偶(1/3)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)31 / 70需要兩套對偶變量：p對應(yīng)流守恒；q對應(yīng)容量約束。最大流的對偶(2/3)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)32 / 70對偶目標必須等于0必須小于等于0最大流的對偶(3/3)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)33 / 70設(shè)置

11、對偶變量取值如下：是對偶可行解嗎？是的。對偶目標函數(shù)的含義？割容量。由強對偶定理可知，若最大流存在最佳解，則最小割問題也存在最佳解。而且最大流等于最小割。對偶的用途：發(fā)現(xiàn)新關(guān)系2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)34 / 70將問題建模為LP模型，進行對偶變換，往往可以發(fā)現(xiàn)新的物理意義，在不同的物理概念之間建立新的聯(lián)系。最大流與最小割之間的關(guān)系就是這樣建立的。最佳路由的對偶(1/4)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)35 / 70需要2套對偶變量：p（流守恒約束）和q（容量約束）。最佳路由的對偶(2/4)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)36 / 70最佳路由的對偶(3/4)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)3

12、7 / 70對偶目標由于z為自由變量，該項系數(shù)必須等于0.該項系數(shù)必須大于等于0.最佳路由的對偶(4/4)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)38 / 70最佳路由=最短路！2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)39 / 70sabt只考慮特定的需求k。其流變量取值大于0的邊構(gòu)成一些路徑。如右圖所示。只看其中的一條路徑（例如sabt）。其他路徑呢（例如sbt）？最佳解在最短路上！權(quán)重設(shè)置2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)40 / 70我們知道，Internet的路由協(xié)議是基于最短路的。控制路由的唯一方法是設(shè)置不同的權(quán)重。最佳路由問題的對偶提供了全新的Insight：怎樣的權(quán)重設(shè)置才是最佳的？根據(jù)優(yōu)化目標建模OR

13、問題。求解OR問題得到的對偶變量取值，就是最佳權(quán)重。需要注意的是：即使得到了最佳權(quán)重，沿著最短路安排流量也不完全等價于原最佳解（因為沒有分流比例信息），應(yīng)該看作是對原最佳解的近似。對偶的用途：Insight2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)41 / 70最佳路由問題與最短路問題表面上看有很大不同，但上述結(jié)論表明，它們具有深層次的聯(lián)系。對偶為我們提供了得到這種“Insight”的一種可能的手段。對偶與整數(shù)規(guī)劃2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)42 / 701234對偶理論對偶問題示例對偶單純形算法簡介整數(shù)規(guī)劃的求解方法5小結(jié)基本思路2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)43 / 70對偶問題也是一個LP問題，也

14、可用單純形算法求解。用單純形法求解對偶問題，相當于保持主問題解的最佳性，追求主問題解的可行性。主問題對偶問題注意以下兩個事實：單純形法的思路是：保持解的可行性，追求解的最佳性。對偶可行實際上意味著RC大于等于0：主問題最佳條件。換基方法2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)44 / 70假定已經(jīng)得到了一個基本解及其基矩陣。由于是基本解，因此等式約束是肯定滿足的。不可行意味著必有某些基變量的取值小于0。對偶單純形法的換基方法是：選擇進基變量時，要保證RC大于等于0 。注意對比主單純形法。例1(1/2)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)45 / 701234考慮一個MCF問題的實例?；仃嚾鐖D紅線所示；流量需

15、求矢量b和邊代價矢量c如圖所示。其它點到節(jié)點4的最短路。該問題求的是什么？流變量取值是多少？RC是多少？顯然，這是一個不可行解，但滿足最優(yōu)條件?？梢杂脤ε紗渭冃畏ㄇ蠼?。例1(2/2)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)46 / 701234對偶單純形法說，先確定出基變量。看誰能保持RC非負。誰入基？已知當前基本解為：換基后，x=？已是可行解，搞定！對偶單純形法的應(yīng)用2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)47 / 70對偶單純形法要求初始解對偶可行（主最佳）。因此同樣需要一個類似大M法那樣的確定初始解的方法。跟直接用單純形法求解主問題有何區(qū)別？若從頭開始求解，那確實沒有區(qū)別。應(yīng)用場景：求解多個關(guān)系密切的LP問

16、題。只是增加了不等式約束只是右端矢量b發(fā)生了變化這些場景的共同特點：第一個問題的最佳解可能不是第二個問題的可行解，但卻滿足第二個問題的最佳條件。因此，可以在第一個問題最佳解的基礎(chǔ)上，應(yīng)用對偶單純形法“繼續(xù)求解”第二個問題。而不必重新開始。場景1：bb2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)48 / 70首先，矩陣A沒有變化。原問題的基矩陣仍是新問題的基矩陣。原問題的最佳基在新問題中一定能保證對偶可行。該解不僅滿足最優(yōu)條件，而且是可行的。該解就是新問題的最佳解。該解不可行，但滿足最優(yōu)條件（對偶可行）。從該解出發(fā)，應(yīng)用對偶單純形法進行換基操作，直至到達某個可行解為止。場景1的第一個例子2014年春季通信網(wǎng)絡(luò)

17、理論基礎(chǔ)49 / 701234節(jié)點1到其它點的最短路。該問題求的是什么？其最佳解是什么？圖中紅線所示。1234右圖求的是什么？其它點到節(jié)點4的最短路。兩個問題有何區(qū)別？只是b不同。最佳解是什么？在原問題解的基礎(chǔ)上，只需一次對偶換基即得到最佳解。場景1的第二個例子(1/2)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)50 / 70saedbc241423322考慮All-Pair最短路問題。可以看作V個單源最短路問題。別傻了！難道你看不出來它們的解有多么相似？那怎么辦？注意到這兩個問題的區(qū)別僅在于矢量b不同。場景1的第二個例子(2/2)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)51 / 70saedbc241423322

18、首先，不妨驗證一下對偶可行性。顯然滿足：因為引入非樹上邊后形成的圈權(quán)重都為正值。第二，檢查新的解是否可行?？梢赃M行對偶換基了。誰出基？誰入基？換基后，解可行嗎？YEAH！只需一次對偶換基即得到最佳解。場景2：增加不等式約束(1/2)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)52 / 70引入該約束后：場景2：增加不等式約束(2/2)2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)53 / 70增加不等式約束后，基矩陣發(fā)生了變化，但同樣滿足：原問題最佳基滿足新問題的最優(yōu)條件。只需檢查原最佳解在新問題中是否可行（只檢查新約束）若可行，則已得到最佳解。若不可行，則可以進行對偶換基。場景2的第一個例子2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)

19、54 / 70saedbc24142332251211假定已經(jīng)求得了單源最短路問題的最佳解，如圖所示。非樹上邊樹上邊顯然，當前解不可行。容易驗證：滿足最優(yōu)條件。采用對偶單純形法求解：對偶換基的結(jié)果如圖。23-1第二次換基的結(jié)果如圖。11已得到可行解。算法結(jié)束。場景2的第二個例子2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)55 / 70saedbc2414233221001假定已經(jīng)求得了單源最短路問題的最佳解，如圖所示。非樹上邊樹上邊必經(jīng)鏈路約束。容易驗證：該解不可行，但滿足最優(yōu)條件。采用對偶單純形法求解：對偶換基的結(jié)果如圖。11已得到可行解。算法結(jié)束。不可行的原因是非基變量不滿足約束。1變量的上下界2014

20、年春季通信網(wǎng)絡(luò)理論基礎(chǔ)56 / 70這兩個例子有兩重作用：對偶單純形法的用途：新問題只是增加了不等式約束。由于新增約束只涉及一個變量，實際上對應(yīng)于變量帶有上下界的LP問題。若用傳統(tǒng)的單純形法求解這類問題，需要將上下界約束變?yōu)榈仁郊s束，合并到矩陣A中去。但這樣往往會導(dǎo)致矩陣A的某些特性發(fā)生變化。例如，帶有容量約束的MCF問題中變量具有上界。若轉(zhuǎn)化為等式約束，會導(dǎo)致系數(shù)矩陣A不再對應(yīng)關(guān)聯(lián)矩陣，從而不能保證基矩陣對應(yīng)生成樹，也不能保證基矩陣的上三角特性。具有上下界的單純形法2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)57 / 70單純形法帶有上下界的單純形法求解最短路問題的網(wǎng)絡(luò)單純形法一般的網(wǎng)絡(luò)單純形法基變量取值

21、非基變量取值退化解基變量=0基變量達到上界或下界樹上邊流量為0樹上邊流量達到上界或下界引入邊j形成的圈中，正向部分流量增加；反向部分流量減小RC的含義引入邊j形成的圈的代價(以邊j的方向為正向)該表羅列了主要的概念上的區(qū)別：對偶與整數(shù)規(guī)劃2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)58 / 701234對偶理論對偶問題示例對偶單純形算法簡介整數(shù)規(guī)劃的求解方法5小結(jié)整數(shù)規(guī)劃的類型2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)59 / 70純純整數(shù)規(guī)劃：所有變量都必須是整數(shù)。混合混合整數(shù)規(guī)劃：只有部分變量具有整數(shù)約束。0-10-1規(guī)劃：全部或部分變量的取值只能是0或1.求解方法：分支定界法2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)60 /

22、 70分支定界法(Branch and Bound)是求解各類整數(shù)規(guī)劃問題的通用解法。我們通過一個例子來展示該算法的各個要點。這個例子是個假想的例子。目的是保持簡單，同時又能展示出所有的關(guān)鍵思想。需要說明的是，該方法并非求解整數(shù)規(guī)劃的唯一方法。其他著名方法包括：Branch and CutCutting Plane在下面的講解過程中，請大家體會該算法的兩個設(shè)計思路：分支的目的是Divide and Conquar。定界的目的是減少分支。要點1：松弛2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)61 / 70LP1ILPB&B算法中，真正求解的是無整數(shù)約束的LP松弛問題：將原問題（ILP）中的整數(shù)約束去掉，所得

23、到的松弛問題。原因很簡單：LP問題很容易求解。求出的解剛好是整數(shù)？分支。你的祈禱應(yīng)驗了。求出的解包含非整數(shù)解？要點2：分支2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)62 / 70LP1LP3LP2ILP分支方法：為什么這樣分支？首先，這種劃分問題的方法不會漏掉原問題的解。第二，LP2和LP3可行域具有整數(shù)邊界：增加了獲得整數(shù)解的機會。第三，由于只是新增了一個不等式約束，因此可以在父問題最佳基的基礎(chǔ)上，用對偶單純形法求解子問題。要點3：下界2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)63 / 70由于子問題比父問題約束更多，因此父問題的最佳目標值是下界。LP1LP3LP2ILP注1：該結(jié)論只適用于LP問題與其樹上子孫之間

24、。注2：ILP雖然是LP1的父親，但不滿足該結(jié)論。事實上，剛好相反：分支樹上所有的LP問題都是ILP的下界。要點4：上界2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)64 / 70LP1LP3LP2ILP假定求解LP2結(jié)果如圖。注意解全是整數(shù)。算法能中止嗎？不，還有其他分支需要探索。LP2還能分支嗎？不僅不能（全是整數(shù)），而且不必（下界）。第一個剪枝(停止分支)條件：得到了整數(shù)解。這是目前碰到的“最好的”原問題可行解。原問題最佳目標值一定小于等于12：稱12為“上界”。將來碰到更好的整數(shù)解時，需要更新上界。要點5：剪枝2014年春季通信網(wǎng)絡(luò)理論基礎(chǔ)65 / 70LP1LP3LP2LP4LP5不可行LP6LP7ILPLP5的后續(xù)分支都不可行。剪枝條件2