通信网理论基础：07-网络优化问题的线性规划建模

1、通信网理论基础Part 07: 网络优化问题的线性规划建模 线性规划建模12线性规划模型的基本概念 最大流问题建模 3最小费用流问题建模 4多商品流问题建模线性规划模型的基本概念线性规划模型的基本组成部分123建模：从一个简单的例子开始如何描述网络中的一个流线性规划模型的组成部分决策变量优化目标约束线性规划模型一般形式的线性规划模型决策变量约束优化目标一个简单的LP建模例子一个公司使用m种原料生产n种不同的产品。假设bi（i = 1, , m） 是第 i 种原料的可用数量。第 j ( j = 1, , n) 种产品需要第i种原料的数量为aij 单位，并且销售一个单位的第 j 种产品可以获利 c

2、j 元。公司生产管理部门需要决策每种产品的生产量以获得最大的利润。生产问题决策变量？ xj : 每种变量产品的生产量优化目标？ 总利润最大约束？ 课堂练习一个医院新成立了一个科室，该科室需要招收一批护士，这些新招收的护士实行轮班制度，每个护士每周连续上5天班，休息两天。该科室在一周的第i天需要护士di个，医院领导希望该科室降低成本，所以要求在满足科室护理要求的情况下，尽量减少招收护士的数量。问题描述该问题的难点在于如何确定决策变量如何对“流”进行建模？一个流用什么决策变量表示？xij: 这个流在链路(i, j) 上的流量一个流必须满足什么约束？流量守恒约束，容量约束SEFBHGCDA怎么用数学

3、模型表达流的约束简单例子用约束标示出从节点1到节点2的一个流，该流的大小为 d1x12x21x13x31d3x32x13x312x32x23x23x21x12dx13 + x12 x31 x21 = dx31 + x32 x13 x23 = 0 x23 + x21 x32 x12 = -d矩阵形式2013年春季通信网络理论基础10 / 50假定：m维矢量x = xijn维矢量b = b(i)矩阵N是什么东西？维度？nm。取值？1或1或0。何时Nij =1？顶点i是边j的起点。何时Nij = 1？顶点i是边j的终点。N : node-arc incidence matrix。流量守恒约束可写为：

4、其中何时Nij = 0？顶点i非边j的终点或起点。流模型的矩阵形式11 / 55图的关联矩阵N，关联矩阵的元素aij=1表示节点i是链路j的tail，元素aij=-1表示节点i是链路j的head，otherwise aij = 0 所以，流量守恒约束可以写为：关联矩阵的第i行乘以流向量x代表什么呢？节点i的出流量减去入流量矩阵N表述的是什么关系？节点和链路的关系所以这种建模方法也称作Node-Link的建模方法其中Node-Link model2013年春季通信网络理论基础12 / 50Node-Link模型网络优化问题的一种建模方法。特点：约束定义在每个顶点(Node)上：流守恒约束变量定义

5、在每条边(Link)上：流变量xij约束的系数矩阵描述的是Node与Link之间的关系：关联矩阵N13 / 70线性规划建模12线性规划模型的基本概念 最大流问题建模 3最小费用流问题建模 4多商品流问题建模14 / 32最大流问题2013年春季给定流网络G，给定节点对(s, t)，求从s到t 的一个流，使得流量值最大(或者只要求得到最大流量值)。决策变量：链路(i, j)上流过的流量优化目标：流的大小最大约束：流守恒约束和容量约束最大流问题2013年春季通信网络理论基础15 / 50变量是什么？xij和v：m+1个。目标函数是线性的吗？约束是线性的吗？是是有多少个约束？每个顶点有一个流守恒约

6、束（等式约束）。每条边有两个约束（不等式约束）。n+2mMF-1线性规划建模12线性规划模型的基本概念 最大流问题建模 3最小费用流问题建模 4多商品流问题建模最小费用流问题建模最小费用流问题建模12最小费用流问题的特例建模这是个什么问题？2013年春季通信网络理论基础18 / 50三个变化：1)maxmin；2)v是给定值；3)目标函数符号说明: cij表示(i, j)上的单位流代价。这是什么问题？最小费用流问题：在节点s和t之间“搬运”v个单位的流，要求费用最小。MCF更一般的最小费用流问题2013年春季通信网络理论基础19 / 50符号说明: b(i)表示顶点i的“需求量”或者“供应量”

7、。需求量为负整数；供应量为正整数。b(i)0，则顶点i为供应节点； b(i)0，则顶点i为需求节点；b(i)=0，则顶点i为转运节点。MCF矩阵形式2013年春季通信网络理论基础20 / 50假定：m维矢量c = cijm维矢量x = xijn维矢量b = b(i)m维矢量u = uijMCFN : node-arc incidence matrix。最小费用流的特例建模最短链路分离路径对问题建模最小费用流的特例建模单源最短路问题建模最大流问题建模单源最短路径问题建模 单源单宿最短路问题给定有向加权图G(V, E)，给定源点/起始点s和宿点/终止点t，求从s出发到t的权重最小的路径。MCF：令

8、b(s) = 1, b(t) = -1b(i) = 0 (i s t)SPM：Shortest Path Model对边上的容量有没有要求？必须大于1。边上容量有意义吗？上述约束只限制了流入流出的差值为1，会不会出现环路？使得目标函数最小的解一定不会出现环路。最短路问题模型分析该模型的最优解会出现多条等价路的情况吗？是的，从理论上讲，该模型的最优解可能是多条等价最短路SPM 1cij, uijx=x12, x23, x14, x42, x43, x13 用MCF模型求解顶点1和3之间的最短路，下面3个解都是最佳的：x1=1,1,0,0,0,0，x2=0,1,1,1,0,0 x3=0.4, 0.

9、7, 0.6, 0.3, 0.3, 012342, 11, 11, 12, 11, 18, 1好意思把x3称作“路”吗？怎么办?2013年春季通信网络理论基础24 / 50解决方法：引入整数约束在单源单宿最短路问题的MCF模型中，加入以下约束：或者整数线性规划问题，或者简称整数规划。0-1规划是整数规划的特例。SPM 2建模技巧1：引入整数变量整数规划问题Project No. 4-12013年春季通信网络理论基础25 / 50Project No.4-1分别用线性规划模型SPM1和整数规划模型SPM2建模单源单宿最短路问题。用Lingo软件求解这两个模型，比较求解时间和求解的结果。用Dijk

10、stra算法求解同样的问题，比较求解时间和结果。主要目的：熟悉基于流变量的建模方法；学习并掌握Lingo软件的使用方法；验证整数约束的效果。这是啥问题？2013年春季通信网络理论基础26 / 50单源多宿最短路问题。一个重要的结论：单源最短路问题是MCF问题的特例。边上的容量u该如何设置？SPM-SSMD必须大于n 1。难道all-pair最短路问题不是？边上容量也有意义吗？SSMD：Single Source Multiple Destination课堂练习2013年春季通信网络理论基础27 / 50带宽约束下的最短路问题给定加权图G，每条边上既有代价cij，也有带宽bij。给定源点s，宿点

11、t，以及带宽需求B。求从s出发到t的带宽大于B的最小权重路径。注意：要求选定的路径带宽大于B，等价于要求具有非零流变量xij的边上带宽大于B。流变量为0的边上呢？没有任何约束。怎样建模？最短链路分离路径对问题建模最短分离路径对问题给定加权图G。给定源点s和宿点d。求从s出发到d的一对路径（两条），要求这两条路径“链路分离”，且路径权重之和最小。MCF:令b(s) = 2, b(t) = -2b(i) = 0 (i s t)边上的容量u该如何设置？必须等于 1。边上容量有意义吗？SDPP-1 & 22013年春季通信网络理论基础29 / 50SDPP：Shortest Disjoint Path

12、 PairSDPP-1SDPP-21SDPP-32013年春季通信网络理论基础30 / 50SDPP-3符号说明：每条边上增加了一个yij变量；bx(s)=by(s)=1；bx(t)=by(t)= 1第三个约束中，不等式右边是m维的全1矢量。第三个约束是什么意思？非零的x和y变量各自构成一条路，并且不重叠。增加整数约束Project No. 4-22013年春季通信网络理论基础31 / 50Project No.4-2用Lingo软件求解SDPP-1 3这3个模型。比较求解时间和求解的结果。最大流：MCF建模2013年春季通信网络理论基础32 / 50最短路问题可以MCF来建模，最大流问题也可

13、以。怎么可能？首先，MF问题中supply和demand没有给定；其次，MF问题中根本没有cost的概念。建模思路：令b(i)=0, for all i V；st增加一条边ts：cts = 1, uts = 1, 令cij=0, for all (i, j) A；求最小费用流意味着什么？为了尽量减小费用，必须在(t, s)上安排尽可能多的流。为了维持流守恒，必须在原网络的s和t之间安排尽可能多的流。MF-2最小生成树：整数约束2013年春季通信网络理论基础33 / 50MST：Minimum Spanning TreeMST-1xij表示边(i,j)是否在生成树上；E(S)表示一个边的子集，这

14、些边的端点均在集合S中。这些约束都是什么意思？xij还是流变量吗？MST-2：辅助变量2013年春季通信网络理论基础34 / 50能不能想办法描述该生成树的权重？直接用流变量乘以边上权重，再求和：不对，流的代价不等于树的代价。流变量非零的边必在生成树上：引入0-1变量yij。要求yij在xij =0时取0，在xij取非零值时取1。M是个足够大的整数。MST-2：模型2013年春季通信网络理论基础35 / 50MST-2请用心体会整数变量的作用。课堂练习2013年春季通信网络理论基础36 / 50施泰纳(Steiner)树问题给定加权图G，以及一个V的子集X，求一棵包含了X中所有顶点的，最小权重

15、的树。怎样建模？线性规划建模12线性规划模型的基本概念 最大流问题建模 3最小费用流问题建模 4多商品流问题建模All-pair最短路：多商品流2013年春季通信网络理论基础38 / 50为什么不能用最小费用流来建模？每个节点需要发出的流为n1，需要收到的流也是n1 。若按照MCF建模，则b(i)=0，无法保证得到n1条路。怎么办？每个节点发出的流不相同：不同的商品。对于第k种商品有，bk(k) = n1, bk(i)= 1(ik)。第k种商品在边(i,j)上的流变量为xkij。APSP-1APSP：All-Pair Shortest PathAPSP-12013年春季通信网络理论基础39 /

16、 50APSP-1由于是求路径，所有的容量约束都没有必要存在。APSP-2：进一步扩展2013年春季通信网络理论基础40 / 50每个节点对之间的流都当作一种“商品”。sk，dk分别表示第k种商品的源点和宿点。APSP-2sk加入容量约束2013年春季通信网络理论基础41 / 50APSP模型中没有容量约束，完全可以划分为多个子问题。加入容量约束呢？最佳路由问题：Optimal Routing最佳路由问题2013年春季通信网络理论基础42 / 50所有节点对之间都有需求，且需求hk都等于1。最佳路由问题给定部分或全部节点对之间的流量需求：给定网络拓扑G(V,E)，边上代价cij，容量uij。共

17、计K个这样的需求，编号k=1, 2, , K第k个需求的大小为hk，源和宿为sk和dk为所有需求寻路，要求目标函数达到最优。显然，上页的模型是最佳路由问题的特例：优化目标是最小化流量代价之和。最佳路由问题的一般模型2013年春季通信网络理论基础43 / 50OR-Generic最佳路由：负载均衡2013年春季通信网络理论基础44 / 50OR-1容量设计问题2013年春季通信网络理论基础45 / 50容量设计问题给定部分或全部节点对之间的流量需求：给定网络拓扑G(V,E)，链路容量的单位成本为cij。共计K个这样的需求，编号k=1, 2, , K第k个需求的大小为hk，源和宿为sk和dk为所有

18、链路设定容量yij，要求总成本最小。注意：为了设计链路容量，必须确定流量安排方式。容量设计问题仍然是流量规划问题，与OR一样；只不过目标函数不同了。容量设计：Node-Link模型2013年春季通信网络理论基础46 / 50CD-1CD：Capacity Dimensioning拓扑设计问题2013年春季通信网络理论基础47 / 50拓扑设计问题给定部分或全部节点对之间的流量需求：给定节点集合V，不给定链路。共计K个这样的需求，编号k=1, 2, , K第k个需求的大小为hk，源和宿为sk和dk确定应该铺设哪些链路，并设定链路容量，要求总成本最小。假定为全连通图拓扑设计：Node-Link模型

19、2013年春季通信网络理论基础48 / 50TD-1TD：TopologyDesign第一种多商品流模型分析在前面的多商品流问题的LP模型中，一个流的路由是通过流量守恒约束来描述的。在前面的模型中，如果流的个数为K个，网络的节点数目为N，那么流量守恒约束有多少个呢？K*N个在前面的模型中，如果流的个数为K个，网络的链路数目为M，那么变量的个数为多少呢？M*K个如果每个节点对间都有一个流，那么前面的LP模型中的约束的个数最多为N3 +N4，变量的个数将最多为N4可见随着网络规模的增加，问题的规模成指数的增长，问题的求解难度也随着急剧的增加解决的办法是什么？ 给定每个流的备选路径集合第二种建模方法

20、假设每个流可能走的路径集合给定每个流从给定的路径集合中挑选一条或者多条路径来承载该流的流量不需要 ，因为使用从源到宿的路径承载流，天然保证了流量守恒约束（与基于增广路径的最大流算法类似）那么，还需要什么约束呢？基于上述假设，模型中还需要流量守恒约束吗？基于上述假设，模型中的决策变量是什么呢？Xdp：流d的第p条被选路上承载的流d的流量流需求约束 容量约束 单个流的流量限制示例(1)51 / 55节点用v表示，链路用e表示，业务需求/流用d 表示 每个业务需求的备选路径集合为：需求d在路径p上的数据流表示为：ce表示链路e的容量v = 2v = 3v = 1d = 1d = 3d = 2v =

21、2v = 4v = 1v = 3e = 4e = 1e = 3e = 2e = 5DemandNetwork示例(2)52 / 55备选路径集v = 2v = 3v = 1h1 = 15v = 2v = 4v = 1v = 3e = 4e = 1e = 3e = 2e = 5DemandNetworkh3 = 10h2 = 20业务需求d=1只有一条路径P11=2，4，2，4的意思是这条路径包含了标号为2和4的两条链路P1=P11业务需求d=2有两条路径，P21=5，P22=3，4业务需求d=3也有两条路径，P31=1，P32=2，3示例(3)53 / 55流需求约束链路容量约束单个流的流量限

22、制链路和路径的关系表达在第二种建模方法中，要得到链路上的使用容量，必须清楚链路和路径之间的关系。他们之间的关系可以用链路-路径（link-path）的关联系数 表示 在给定路径列表和每条路径所包含链路的情况下， 是一个定值。因为这个系数的引进，我们可以将链路e上的流量用下面的式子表示：从而容量约束可以写成：第二种建模方法叫做Link-Path的建模方式第二种建模方法分析55 / 55决策变量的个数是多少D*Pd约束的个数是多少？D+2M如果任意两点间都有一个流，并且网络是Full-Mesh的情况下，变量的个数为N2*Pd，约束的个数为3N2第二种建模方法的优点是什么？问题的规模可以控制第二种建

23、模方法的缺点是什么？求得的解不一定最优容量设计：Link-Path模型2013年春季通信网络理论基础56 / 50CD-2CD：Capacity Dimensioning拓扑设计：Link-Path模型2013年春季通信网络理论基础57 / 50TD-2TD：Topology DesignNode-Link vs. Link-Path(1/2)2013年春季通信网络理论基础58 / 50以容量规划问题为例。CD-2: Link-PathCD-1: Node-Link变量数目？约束数目？变量数目？约束数目？符号说明：Node-Link vs. Link-Path(2/2)2013年春季通信网络理论基础59 / 50以容量规划问题为例。CD-2: Link-PathCD-1: Node-Link变量数目？约束数目？变量数目？约束数目？结论：Link-Path模型求得的解不是最佳解，除非备选路径集合中包含了原图中所有的路径。Projec