1、通信网理论基础,虞红芳教授 博导,Part 07:网络优化问题的线性规划建模,线性规划建模,1,2,线性规划模型的基本概念,最大流问题建模,4,多商品流问题建模,线性规划模型的基本概念,线性规划模型的基本组成部分,1,2,3,建模：从一个简单的例子开始,如何描述网络中的一个流,线性规划模型的组成部分,决策变量,优化目标,约束,线性规划模型,一般形式的线性规划模型,决策变量,约束,优化目标,一个简单的LP建模例子,决策变量？,xj:每种变量产品的生产量,优化目标？,总利润最大,约束？,课堂练习,如何对“流”进行建模？,xij:这个流在链路(i,j)上的流量,流量守恒约束，容量约束,S,E,F,B
2、,H,G,C,D,A,简单例子,用约束标示出从节点1到节点2的一个流，该流的大小为 d,1,x12,x21,x13,x31,d,3,x32,x13,x31,2,x32,x23,x23,x21,x12,d,x13+x12 x31 x21=d,x31+x32 x13 x23=0,x23+x21 x32 x12=-d,矩阵形式,2013年春季通信网络理论基础,10/50,假定：,nm。,1或1或0。,顶点i是边j的起点。,顶点i是边j的终点。,顶点i非边j的终点或起点。,流模型的矩阵形式,11/55,节点i的出流量减去入流量,节点和链路的关系,所以这种建模方法也称作Node-Link的建模方法,其中
3、,Node-Link model,2013年春季通信网络理论基础,12/50,网络优化问题的一种建模方法。,特点：,约束定义在每个顶点(Node)上：流守恒约束,变量定义在每条边(Link)上：流变量xij,约束的系数矩阵描述的是Node与Link之间的关系：关联矩阵N,13/70,线性规划建模,1,2,线性规划模型的基本概念,最大流问题建模,4,多商品流问题建模,14/32,最大流问题,2013年春季,给定流网络G，给定节点对(s,t)，求从s到t 的一个流，使得流量值最大(或者只要求得到最大流量值)。,决策变量：链路(i,j)上流过的流量,优化目标：流的大小最大,约束：流守恒约束和容量约束
4、,最大流问题,2013年春季通信网络理论基础,15/50,xij和v：m+1个。,是,是,每个顶点有一个流守恒约束（等式约束）。,每条边有两个约束（不等式约束）。,n+2m,MF-1,线性规划建模,1,2,线性规划模型的基本概念,最大流问题建模,3,最小费用流问题建模,4,多商品流问题建模,最小费用流问题建模,最小费用流问题建模,1,2,最小费用流问题的特例建模,这是个什么问题？,2013年春季通信网络理论基础,18/50,最小费用流问题：在节点s和t之间“搬运”v个单位的流，要求费用最小。,MCF,更一般的最小费用流问题,2013年春季通信网络理论基础,19/50,MCF,矩阵形式,2013
5、年春季通信网络理论基础,20/50,假定：,MCF,最小费用流的特例建模,最短链路分离路径对问题建模,最小费用流的特例建模,单源最短路问题建模,最大流问题建模,单源最短路径问题建模,MCF：,令b(s)=1,b(t)=-1b(i)=0(i s t),SPM：Shortest Path Model,必须大于1。,使得目标函数最小的解一定不会出现环路。,最短路问题模型分析,是的，从理论上讲，该模型的最优解可能是多条等价最短路,SPM 1,cij,uij,x=x12,x23,x14,x42,x43,x13,用MCF模型求解顶点1和3之间的最短路，下面3个解都是最佳的：x1=1,1,0,0,0,0，x
6、2=0,1,1,1,0,0 x3=0.4,0.7,0.6,0.3,0.3,0,怎么办?,2013年春季通信网络理论基础,24/50,解决方法：引入整数约束,或者,整数线性规划问题，或者简称整数规划。0-1规划是整数规划的特例。,SPM 2,建模技巧1：引入整数变量,整数规划问题,Project No.4-1,2013年春季通信网络理论基础,25/50,这是啥问题？,2013年春季通信网络理论基础,26/50,单源多宿最短路问题。,SPM-SSMD,必须大于n 1。,SSMD：Single Source Multiple Destination,课堂练习,2013年春季通信网络理论基础,27/5
7、0,没有任何约束。,最短链路分离路径对问题建模,MCF:,令b(s)=2,b(t)=-2b(i)=0(i s t),必须等于 1。,SDPP-1&2,2013年春季通信网络理论基础,29/50,SDPP：Shortest Disjoint Path Pair,SDPP-1,SDPP-2,1,SDPP-3,2013年春季通信网络理论基础,30/50,SDPP-3,非零的x和y变量各自构成一条路，并且不重叠。,增加整数约束,Project No.4-2,2013年春季通信网络理论基础,31/50,最大流：MCF建模,2013年春季通信网络理论基础,32/50,最短路问题可以MCF来建模，最大流问题
8、也可以。,MF-2,最小生成树：整数约束,2013年春季通信网络理论基础,33/50,MST：Minimum Spanning Tree,MST-1,MST-2：辅助变量,2013年春季通信网络理论基础,34/50,直接用流变量乘以边上权重，再求和：不对，流的代价不等于树的代价。,流变量非零的边必在生成树上：引入0-1变量yij。,要求yij在xij=0时取0，在xij取非零值时取1。,M是个足够大的整数。,MST-2：模型,2013年春季通信网络理论基础,35/50,MST-2,课堂练习,2013年春季通信网络理论基础,36/50,线性规划建模,1,2,线性规划模型的基本概念,最大流问题建模
9、,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：All-Pair Shortest Path,APSP-1,2013年春季通信网络理论基础,39/50,APSP-1,APSP-2：进一步扩展,2013年春季通信网络理论基础,40/50,每个节点对之间的流
10、都当作一种“商品”。,APSP-2,sk,加入容量约束,2013年春季通信网络理论基础,41/50,APSP模型中没有容量约束，完全可以划分为多个子问题。,最佳路由问题：Optimal Routing,最佳路由问题,2013年春季通信网络理论基础,42/50,所有节点对之间都有需求，且需求hk都等于1。,给定部分或全部节点对之间的流量需求：,给定网络拓扑G(V,E)，边上代价cij，容量uij。,显然，上页的模型是最佳路由问题的特例：,优化目标是最小化流量代价之和。,最佳路由问题的一般模型,2013年春季通信网络理论基础,43/50,OR-Generic,最佳路由：负载均衡,2013年春季通信
11、网络理论基础,44/50,OR-1,容量设计问题,2013年春季通信网络理论基础,45/50,给定部分或全部节点对之间的流量需求：,给定网络拓扑G(V,E)，链路容量的单位成本为cij。,容量设计问题仍然是流量规划问题，与OR一样；只不过目标函数不同了。,容量设计：Node-Link模型,2013年春季通信网络理论基础,46/50,CD-1,CD：Capacity Dimensioning,拓扑设计问题,2013年春季通信网络理论基础,47/50,给定部分或全部节点对之间的流量需求：,给定节点集合V，不给定链路。,拓扑设计：Node-Link模型,2013年春季通信网络理论基础,48/50,T
12、D-1,TD：TopologyDesign,第一种多商品流模型分析,K*N个,M*K个,可见随着网络规模的增加，问题的规模成指数的增长，问题的求解难度也随着急剧的增加,给定每个流的备选路径集合,第二种建模方法,每个流可能走的路径集合给定,每个流从给定的路径集合中挑选一条或者多条路径来承载该流的流量,不需要，因为使用从源到宿的路径承载流，天然保证了流量守恒约束（与基于增广路径的最大流算法类似）,Xdp：流d的第p条被选路上承载的流d的流量,流需求约束,容量约束,单个流的流量限制,示例(1),51/55,节点用v表示，链路用e表示，业务需求/流用d 表示,每个业务需求的备选路径集合为：,需求d在路
13、径p上的数据流表示为：,ce表示链路e的容量,v=2,v=3,v=1,d=1,d=3,d=2,v=2,v=4,v=1,v=3,e=4,e=1,e=3,e=2,e=5,Demand,Network,示例(2),52/55,备选路径集,v=2,v=3,v=1,h1=15,v=2,v=4,v=1,v=3,e=4,e=1,e=3,e=2,e=5,Demand,Network,h3=10,h2=20,示例(3),53/55,链路和路径的关系表达,第二种建模方法叫做Link-Path的建模方式,第二种建模方法分析,55/55,D*Pd,D+2M,问题的规模可以控制,求得的解不一定最优,容量设计：Link-
14、Path模型,2013年春季通信网络理论基础,56/50,CD-2,CD：Capacity Dimensioning,拓扑设计：Link-Path模型,2013年春季通信网络理论基础,57/50,TD-2,TD：Topology Design,Node-Link vs.Link-Path(1/2),2013年春季通信网络理论基础,58/50,以容量规划问题为例。,Node-Link vs.Link-Path(2/2),2013年春季通信网络理论基础,59/50,以容量规划问题为例。,Project 5,2013年春季通信网络理论基础,60/50,每个节点对间的流量为150M每条链路容量如图中所
15、示每条链路的代价为1优化目标是最小化最大链路利用率,要求：分别使用node-link和link-path的方式对该问题进行建模，求解出使得最大链路利用率最小的业务路由和流量分配方案。Link-path模型求解时如果备选路径集合给定3条，5条，7条的情况下分析求出的解的变化情况，以及求解时间的变化情况并分析原因。对比link-path模型（3条备选路时）和node-link模型求出的优化目标值是否一样，如果不一样请说明原因。对比link-path模型（3条备选路时）和node-link模型求解时间哪个更长，并分析原因.,小结：问题与模型,2013年春季通信网络理论基础,61/50,旧问题,新问题,小结：建模方法,2013年春季通信网络理论基础,62/50,End of Part 07,The solution of LP is right there!,
