通信网络理论基础-对偶与整数规划-2010-FINAL-Yu.pptx

通信网络理论基础,虞红芳 博士 教授 博导,Part 09: 对偶与整数规划,对偶与整数规划,2013年春季 通信网络理论基础,2 / 70,1,2,3,4,对偶理论,对偶问题示例,对偶单纯形算法简介,整数规划的求解方法,拉格朗日乘子法,2013年春季 通信网络理论基础,3 / 70, + +=,先构造拉格朗日函数： , = + +(),求偏导，并令偏导等于0：=; =,最佳解为：=/,由原问题的约束+=，可得：=,故，最佳解为：=/,LP标准型的对偶(1/2),2013年春季 通信网络理论基础,4 / 70, = ,松弛掉等式约束可得：, +() ,任意给定一个p，松弛问题的最佳目标值()都是原问题 最佳目标值 的下界。,故：求解问题 等价于求解原问题的最佳估值。,LP标准型的对偶(2/2),2013年春季 通信网络理论基础,5 / 70,重写 ： = +() =+ ,既然目标是最大化 ， 没有意义。, ,关于对偶的第一个印象,2013年春季 通信网络理论基础,6 / 70,Well，至少对标准型，是这样。,我们用一个例子来说明。,例子：一般的LP(1/4),2013年春季 通信网络理论基础,7 / 70, + + + + = , , = + + + + + + (+ ),松弛问题变为： = , , (,),在该松弛问题中，为了体现“惩罚”的含义，必有：,例子：一般的LP(2/4),2013年春季 通信网络理论基础,8 / 70, + + + + = , , = + + + + + + (+ ),为了保证最小化Lagrange函数有意义，必有：, , = + + + + + + + ,例子：一般的LP(3/4),2013年春季 通信网络理论基础,9 / 70, + + + + = ,由于对偶约束与对应的主变量“同符号”，其最小值为0。, , = + + + + + + + ,松弛问题为： = , , (,), = + + ,显然， 是原问题目标值的下界。,例子：一般的LP(4/4),2013年春季 通信网络理论基础,10 / 70, + + + + = , + + + + =,主问题,对偶问题,总结上述推导，可得：,关于对偶的第二个印象,2013年春季 通信网络理论基础,11 / 70,另一个例子(1/4),2013年春季 通信网络理论基础,12 / 70, + + + + = ,应用“惩罚”的概念推导下面最大化问题的对偶问题。, , = + + + + + + + ( ), , , ,另一个例子(2/4),2013年春季 通信网络理论基础,13 / 70, + + + + = ,应用“惩罚”的概念推导下面最大化问题的对偶问题。, , = + + + + + + + ( ), + , , = + + + + + + (+ ) , ,+ =,另一个例子(3/4),2013年春季 通信网络理论基础,14 / 70, + + + + = ,松弛问题为： = , , (,), , = + + + + + + (+ ) ,对偶约束与对应的主变量“符号相反”，其最大值为0。, = + + ,显然， 是原问题目标值的上界。,最小化 等价于求原问题的最佳估值。,另一个例子(4/4),2013年春季 通信网络理论基础,15 / 70, + + + + = , + + + + =,主问题,对偶问题,总结上述推导，可得：,该例中，主问题是上例中的对偶问题。,该例中，对偶问题是上例中的主问题。,关于对偶的第三个印象,2013年春季 通信网络理论基础,16 / 70,主问题可以推出其对偶问题。,对偶问题也可以推出其对应的主问题。,让我们来讨论对偶理论中最深刻的结论：对偶定理。,弱对偶定理,2013年春季 通信网络理论基础,17 / 70, , = ,主问题,对偶问题,推导对偶问题的过程中，我们知道：,故有：,两个推论,2013年春季 通信网络理论基础,18 / 70,主问题最佳值为, 要求对偶问题目标值小于等于。,对任一主可行解y都有x为主最佳解。,强对偶定理(1/2),2013年春季 通信网络理论基础,19 / 70,假定用单纯形法求解主问题，得到最佳解x和最佳基B，则：,令= ，则有：, , = ,主问题,对偶问题,另一方面，由于： = = =,强对偶定理(2/2),2013年春季 通信网络理论基础,20 / 70, , = ,主问题,对偶问题,若标准型主问题存在最佳解，则单纯形法一定可以求出。,求出了主最佳解，则对偶最佳解也被求出了。,因此，有：,任一LP问题都可以转化为标准型。,关于对偶的第四个印象,2013年春季 通信网络理论基础,21 / 70,二者的最佳目标值是一致的：估值是精确的。,求解主问题的同时，对偶问题的解也被求出了。,一个重要的结论：互补松弛定理。,互补松弛定理(1/2),2013年春季 通信网络理论基础,22 / 70,证明：,互补松弛定理(2/2),2013年春季 通信网络理论基础,23 / 70, + =,证明：, =, ，并且 =, 。,充要条件得证。,关于对偶的第五个印象,2013年春季 通信网络理论基础,24 / 70,若主最佳解非零，则对应的对偶约束必取等号。, =, .,若对偶最佳解非零，则对应的主约束必取等号。, =, ,对偶与整数规划,2013年春季 通信网络理论基础,25 / 70,1,2,3,4,对偶理论,对偶问题示例,对偶单纯形算法简介,整数规划的求解方法,最短路的对偶(1/2),2013年春季 通信网络理论基础,26 / 70, (,) :(,) : , = :(,) : , =, , (,), , = , + + + + ,最短路的对偶(2/2),2013年春季 通信网络理论基础,27 / 70, , = , + + + + ,变形可得： , = + , ( + ) , + , (,),绳球模型,2013年春季 通信网络理论基础,28 / 70, + , (,),令 = ， =， 可得：, + , (,),绳球模型。,一手拿s，一手拿i，拉伸到 不能再拉为止。,最大化 ，但需满足约束。,Bellman-Ford算法,2013年春季 通信网络理论基础,29 / 70, + , (,),显然，在该约束下能达到的 最大距离标记 必然满足： = , () ( + ) , 其中()为指向j的边的集合。,迭代求解。第k+1次迭代使用第k次的迭代结果： + = , () ( + ) , ,Yes, its Bellman-Ford algorithm!,事实上，上述方程成为Bellman方程。,绳球模型：先将s上的绳子拉直，然后将s邻接点的绳子 拉直；一直进行下去，直至所有点i到s的绳子都被拉直。,对偶的用途：设计新算法,2013年春季 通信网络理论基础,30 / 70,Bellman-Ford算法求解的其实不是最短路，而是 距离标记（对偶变量）。,最大流的对偶(1/3),2013年春季 通信网络理论基础,31 / 70, :(,) : , = = , = (,), , =+ + + + + , + + , ( ),显然有, 。,最大流的对偶(2/3),2013年春季 通信网络理论基础,32 / 70, , =+ + + + + , + + , ( ),变形可得： , = , + + + (,) + ,最大流的对偶(3/3),2013年春季 通信网络理论基础,33 / 70, , = + , (,) , (,),令(,)表示顶点和之间的 任一割集，, 。,设置对偶变量取值如下：,是的。,割容量。,对偶的用途：发现新关系,2013年春季 通信网络理论基础,34 / 70,最大流与最小割之间的关系就是这样建立的。,最佳路由的对偶(1/4),2013年春季 通信网络理论基础,35 / 70, : , : , = , =, : , : , = , =, : , , , : , , , =, =, , (,) , , (,),最佳路由的对偶(2/4),2013年春季 通信网络理论基础,36 / 70, , =+ = + + = + + = , ( + ) + , = ,显然有, 。,最佳路由的对偶(3/4),2013年春季 通信网络理论基础,37 / 70,变形可得： , = = ( ) + + , + = , ,对偶目标,由于z为自由变量， 该项系数必须等于0.,该项系数必须大于等于0.,最佳路由的对偶(4/4),2013年春季 通信网络理论基础,38 / 70, = ( ) , = + , , , , (,),令 = ，可得：,假定主问题最佳解中， 取值大于0，则根据 互补松弛定理可知，其 对应的对偶约束取等号 即： + =,最佳路由=最短路！,2013年春季 通信网络理论基础,39 / 70,若最佳解中 取值大于0，则有： + =,只考虑特定的需求k。其流变量取值大于0的边构成一些 路径。如右图所示。,只看其中的一条路径（例如sabt）。, + = + = + =,求和可得：若以 为权重， 该路径长度 = , + + =,求和可得：若以 为权重， 该路径长度 ,最佳解在最短路上！,权重设置,2013年春季 通信网络理论基础,40 / 70,我们知道，Internet的路由协议是基于最短路的。,控制路由的唯一方法是设置不同的权重。,最佳路由问题的对偶提供了全新的Insight：,对偶的用途：Insight,2013年春季 通信网络理论基础,41 / 70,对偶与整数规划,2013年春季 通信网络理论基础,42 / 70,1,2,3,4,对偶理论,对偶问题示例,对偶单纯形算法简介,整数规划的求解方法,基本思路,2013年春季 通信网络理论基础,43 / 70,对偶问题也是一个LP问题，也可用单纯形算法求解。,用单纯形法求解对偶问题，相当于保持主问题解的 最佳性，追求主问题解的可行性。, , = ,主问题,对偶问题,换基方法,2013年春季 通信网络理论基础,44 / 70,假定已经得到了一个基本解及其基矩阵。,由于是基本解，因此等式约束是肯定满足的。不可行 意味着必有某些基变量的取值小于0。,对偶单纯形法的换基方法是：,例1(1/2),2013年春季 通信网络理论基础,45 / 70,考虑一个MCF问题的实例。基矩阵如图红线所示； 流量需求矢量b和边代价矢量c如图所示。,其它点到节点4的最短路。, , , , , =(,),(,), , , , , =(,),例1(2/2),2013年春季 通信网络理论基础,46 / 70,1,2,3,4, =, =, =, =, =, =, =, =, =, , , , , =(,),对偶单纯形法说， 先确定出基变量。,显然应该是 出基。,看谁能保持RC非负。,已知当前基本解为：, =, =, =, =, , , , , =(,),对偶单纯形法的应用,2013年春季 通信网络理论基础,47 / 70,对偶单纯形法要求初始解对偶可行（主最佳）。因此同样 需要一个类似大M法那样的确定初始解的方法。,若从头开始求解，那确实没有区别。,应用场景：求解多个关系密切的LP问题。,只是增加了 不等式约束,只是右端矢量b 发生了变化,这些场景的共同特点：第一个问题的最佳解可能不是第 二个问题的可行解，但却满足第二个问题的最佳条件。,因此，可以在第一个问题最佳解的基础上，应用对偶单 纯形法“继续求解”第二个问题。而不必重新开始。,场景1：bb,2013年春季 通信网络理论基础,48 / 70,首先，矩阵A没有变化。,原问题的基矩阵仍是新问题的基矩阵。,其次，RC的计算与b无关： = ,原问题的最佳基在新问题中一定能保证对偶可行。,根据原问题的基矩阵计算新问题的基本解： = ,该解不仅满足最优条件，而且是可行的。,该解就是新问题的最佳解。,该解不可行，但满足最优条件（对偶可行）。,从该解出发，应用对偶单纯形法进行换基操作， 直至到达某个可行解为止。,场景1的第一个例子,2013年春季 通信网络理论基础,49 / 70,节点1到其它点的最短路。,图中红线所示。,其它点到节点4的最短路。,只是b不同。,场景1的第二个例子(1/2),2013年春季 通信网络理论基础,50 / 70,考虑All-Pair最短路问题。,别傻了！难道你看不出来它们的解有多么相似？,注意到这两个问题的区别仅在于矢量b不同。,不妨考虑对偶单纯形算法：在()最佳解的 基础上去求解()。,场景1的第二个例子(2/2),2013年春季 通信网络理论基础,51 / 70,首先，不妨验证一下对偶可行性。,第二，检查新的解是否可行。,可以进行对偶换基了。,只有 满足条件。,只有 满足条件。,YEAH！,场景2：增加不等式约束(1/2),2013年春季 通信网络理论基础,52 / 70,假定新的约束为： + +,转换为等式约束，得： + + + = +,引入该约束后：,构造矩阵： = ,+ (+)矩阵,行列式非零： =|+1,故，是的基矩阵。,场景2：增加不等式约束(2/2),2013年春季 通信网络理论基础,53 / 70,考察新问题的Reduced Cost： = = + =( ) ,注意： =, ,只需检查原最佳解在新问题中是否可行（只检查新约束）,场景2的第一个例子,2013年春季 通信网络理论基础,54 / 70,5,1,2,1,1,假定已经求得了单源最短路问题的最佳解，如图所示。,非树上边,树上边, , ,现增加约束： ,显然，当前解不可行。,容易验证：满足最优条件。,采用对偶单纯形法求解：,2,3,-1,1,1,场景2的第二个例子,2013年春季 通信网络理论基础,55 / 70,1,0,0,1,假定已经求得了单源最短路问题的最佳解，如图所示。,非树上边,树上边, , ,现增加约束： ,必经链路约束。,容易验证：该解不可行， 但满足最优条件。,采用对偶单纯形法求解：,1,1,先定入基变量： ,1,变量的上下界,2013年春季 通信网络理论基础,56 / 70,这两个例子有两重作用：,若用传统的单纯形法求解这类问题，需要将上下界 约束变为等式约束，合并到矩阵A中去。,但这样往往会导致矩阵A的某些特性发生变化。例 如，带有容量约束的MCF问题中变量具有上界。 若转化为等式约束，会导致系数矩阵A不再对应关 联矩阵，从而不能保证基矩阵对应生成树，也不能 保证基矩阵的上三角特性。,解决方法是：将上下界约束看成是跟标准型中的不 等式约束()同样的约束，不合并入A矩阵。,具有上下界的单纯形法,2013年春季 通信网络理论基础,57 / 70,该表罗列了主要的概念上的区别：,对偶与整数规划,2013年春季 通信网络理论基础,58 / 70,1,2,3,4,对偶理论,对偶问题示例,对偶单纯形算法简介,整数规划的求解方法,整数规划的类型,2013年春季 通信网络理论基础,59 / 70,求解方法：分支定界法,2013年春季 通信网络理论基础,60 / 70,分支定界法(Branch and Bound)是求解各类整数规划 问题的通用解法。,我们通过一个例子来展示该算法的各个要点。,这个例子是个假想的例子。目的是保持简单，同时又能 展示出所有的关键思想。,需要说明的是，该方法并非求解整数规划的唯一方法。 其他著名方法包括：,在下面的讲解过程中，请大家体会该算法的两个设计思路：,要点1：松弛,2013年春季 通信网络理论基础,61 / 70,LP1,ILP,B&B算法中，真正求解的是无整数约束的LP松弛问题： 将原问题（ILP）中的整数约束去掉，所得到的松弛问题。,原因很简单：LP问题很容易求解。,分支。,你的祈祷应验了。,图例： , , ,.,.,. .,要点2：分支,2013年春季 通信网络理论基础,62 / 70,图例： , , ,LP1,.,.,. .,LP3,LP2,ILP, , ,分支方法：,首先，这种划分问题的方法不会漏掉原问题的解。,第二，LP2和LP3可行域具有整数边界：增加了获得 整数解的机会。,第三，由于只是新增了一个不等式约束，因此可以在 父问题最佳基的基础上，用对偶单纯形法求解子问题。,要点3：下界,2013年春季 通信网络理论基础,63 / 70,图例： , , ,LP1,.,.,. .,LP3,LP2,ILP, , ,要点4：上界,2013年春季 通信网络理论基础,64 / 70,图例： , , ,LP1,.,.,. .,LP3,LP2, ,ILP, , ,假定求解LP2结 果如图。注意解 全是整数。,不，还有其他 分支需要探索。,不仅不能（全是整数），而且不必（下界）。,第一个剪枝(停止分支)条件：得到了整数解。,原问题最佳目标值一定小于等于12：称12为“上界”。,将来碰到更好的整