网络优化问题建模

d
xd1 xd 2 xdPd hd
对于每个业务需求d，我们可以写出下面 的等式： Pd xdp hd , d 1, 2,, D
p 1
容量约束
对于一条链路e,它上面的流向量之和不能 超过其容量Ce或ye，从而有下面的约束： x31 y1
x11 x32 y2 x22 x32 y3 x11 x22 y4 x21 y5
ye表示链路e上需要配置的容量
路径集合
业务需求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}。
业务需求约束
我们需要在保证使用的代价最小的情况下， 确定网络的每条链路容量。
例子
右图的网络有四个节点，五条无 向链路，V=4，E=5。图上面部 分表示有三个无向业务需求对， D=3。
节点用v（v=1，2，…，V）表示， 链路用e(e=1,2,…，E)表示，业务 需求用d (d=1,2,…，D)表示
符号说明
每一个业务需求d都指定了一些能发送流的路径。 指定的路径用p=1,2,…pd表示，pd是路径数目总 和；这些路径称为备选路径集。
我们将业务需求d的路径列表写成下面的形式： ，每条路径连接需求d的源目节点 P d (P d1 , P d 2 ,, P dP )
d
xdp ( p 1, 2,, P 需求d在路径p上的数据流表示为： d)
Node-Link方式描述，主要包括两大部分 约束： (1) 业务路由和业务需求量约束
(2) 链路容量约束
符号说明
x ij ：表示节点i和j间的业务在链路(m, n)上使 mn 用的容量。
ymn: 表示链路(m,n)上需要配置的容量。
业务路由和业务需求量约束
在Node-Link的描述中，每个业务都有这样 一组约束，比如针对节点1和节点2间的业 务有下列约束：
LP Formulation for Capacitated Problem （Linkpath）
Min F e e ye

d
p
xdp hd , d 1, 2, , D.
edp xdp ye , e 1, 2, , E.

p
ye Ce , e 1,..., E
链路和路径的关系
我们要得到链路负载，必须清楚链路和路径之间 的关系。他们之间的关系可以用链路-路径（linkpath）的关联系数 edp 表示
edp
1(如果e属于需求d的路径p) 0(如果e不属于需求d的路径p)
一般化的链路容量表示
在给定路径列表和每条路径所包含链路的情况 下， edp 是一个定值。因为这个系数的引进，我们 可以将链路e上的负载用下面的式子表示：
( m , n )E

ij xmn
( n , m )E

ij xnm 0, i, j D, m i j
( n , j )E

ij xnj
( j , n )E

xij jn hij , i , j D
i , j D

ij xmn ymn
流量守恒约束
思考
Node-Link建模和Link-path建模各自有什么 优缺点？
网络拓扑设计
已知条件
•网络中节点间的业务需求hd •网络中每条链路e的单位成本 •网络中每条链路的架设成本
优化目标
业务使用的总的网络链路和总的网络架设 成最小.
网络拓扑设计（建模）
采用Link-Path 建模如下：
也可以更一般化的写成：
F e ye e ye
e 1 e E
完整模型
一般化的完整模型
F e ye
x
p
e
dp
hd , d 1, 2,, D
edp dp

d p
x ye , e 1, 2,, E
x 0, y 0
用Node-Link方式来描述
D V E 1 V 2 (V 1) V (V 1) O(V 3 ) 2
Capacitated Problem（容量受限的 设计问题）
已知条件
•网络中节点间的业务需求hd •网络中每条链路e的代价πe •网络中每条链路e的容量Ce •网络拓扑G（V，E）
优化目标
通过设计业务路由和每条路由上的流量分 配，使得花费的代价最少
常数：
edp =1，如果路径p经过链路e
e
变量：
xdp
hd
=0，如果路径p不经过链路e 需求d的大小 链路e的单位使用代价 业务d在路径p上分配的流量
ye
链路e的使用容量
LP Formulation for Uncapacitated Problem （Link-path）
Min F e e ye

d 1 p 1
D
Pd
edp dp
x
从而容量约束可以写成：

d p
edp dp
x ye , e 1, 2,, E
目标函数
目标函数可以写成：
F 1 y1 2 y2 3 y3 4 y4 5 y5 2 y1 y2 y3 3 y4 y5
Min F e e ye
hd , if v sd , a x b x e ev ed e ev ed 0, if v sd , td , v 1, 2,,V d 1, 2,, D h , if v td , d

d
xed ye , e 1, 2,, E.

p
xdp e e edp d

p
Ldp xdp
S.t:

x h , d 1, 2, , D . dp d p
符号说明(Node-link)
标号：
d 1, 2, , D 业务需求标号
e 1, 2, , E 网络链路标号
v 1, 2, , V 节点标号
x x x x h12
12 12 12 32 12 wenku.baidu.com1 12 23
x x x x 0
12 31 12 32 12 13 12 21 12 23
x x x x h12
12 12 12 32 12 23
流量守恒图示
12 x13
12 x31
h12
1
12 x12
12 x32
思考题
如果网络中链路的容量是不足的，即上面 的模型没有可行解，那么现在要求求解每 条链路上最少需要增加多少容量ze，应该 怎么建模？
扩容问题
Min
F ze
e

p
xdp hd , d 1, 2, , D.
edp xdp ze Ce , e 1, 2,, E.
Node-link和Link-path的比较
变量数目
Link-path
P D E 1 P V (V 1) k v O (V 2 ) 2
约束个数
DE 1 V (V 1) k V O (V 2 ) 2
Node-link
ED E 1 1 k V V (V 1) k V O (V 3 ) 2 2
符号说明(Link-path)
标号：
d 1, 2, , D 业务需求标号
e 1, 2, , E 网络链路标号
p 1, 2,, Pd 路径标号
常数：
edp =1，如果路径p经过链路e
e
Ce 变量： xdp
hd
=0，如果路径p不经过链路e 需求d的大小 链路e的单位使用代价 链路e的容量 业务d在路径p上分配的流量
2
4.2 建模技巧
3.3 建模方法和技巧
1
Uncapacitated and Capacitated problem
2
3 4
Routing Restrictions
Modular Flows and Links
Convex Cost
Uncapacitated Problem（容量不受 限的设计问题）
x12 23
3
12 x13
x
12 31
x 32
2
x
12 21
12
12 x12
h12
x12 21
x12 23
节点1
节点2
节点3
容量约束
假设网络中有2个业务，分别为<1,2>和 <3,2>,那么针对链路（1，2）的容量约束可 以写成：
x x y12
12 12 32 12
优化目标
最小化是使用的链路代价
min F e e ye e ke ue subject to :
x
p d
dp p
hd
edp xdp ye
ye C ue x 0, y 0
练习题
使用Node-Link的描述方式求解出节点1 和6间的最短路径，只需要写出模型。
本章主要内容
1
4.1网络建模基本方法

d
x hd , d 1, 2, , D. p dp
p
需求约束

edp xdp ye , e 1, 2,, E.
LP Formulation for Uncapacitated Problem （Link-path）
min F e e d

p
edp xdp d
第四章 网络优化介绍和建模
（Introduction to Network Optimization）
虞红芳 博士 副教授
宽带光纤传输与通信网技术重点实验室
本章主要内容
1
4.1网络建模基本方法
2
4.2 建模技巧
容量设计问题
给定网络拓扑G（V，E）和网络业务需求 矩阵D。 这些给定的业务可以在不同的路径上路由。
已知条件
•网络中节点间的业务需求hd •网络中每条链路e的代价πe •网络拓扑G（V，E）
优化目标
通过设计业务路由和每条路由上的流量分 配，使得每条链路上容量代价之和最少
符号说明(Link-path)
标号：
d 1, 2, , D 业务需求标号
e 1, 2, , E 网络链路标号
p 1, 2,, Pd 路径标号

d
p
3.3 建模方法和技巧
1
Uncapacitated and Capacitated problem
2
3 4
Routing Restrictions
Modular Flows and Links
Convex Cost
Routing Restrictions（路由限制）
已知条件
•网络中节点间的业务需求hd •网络中每条链路e的代价πe •网络中每条链路e的容量Ce •网络拓扑G（V，E）
常数： aev =1，如果节点v是链路e的起点 =0，其他 bev =1，如果节点v是链路e的终点 =0，其他 需求d的大小 hd e 链路e的单位使用代价 sd 业务d的源节点
td
业务d的目的节点 业务d在链路e上占用的带宽 链路e的使用容量
变量：
xde ye
LP Formulation for Uncapacitated Problem（Node-link）
每一个业务需求的需求量需要通过它 的路径列表中各条路径上的业务流来 承载，我们写出下面的几个等式
x11 15 x21 x22 20 x31 x32 10
一般化的业务需求约束表示
假设我们用矢量 xd ( xd1, xd 2 ,, xdP )来表示指 定给业务需求d的路径P =1,2,…Pd上的业务 流向量，则下面等式成立：
min 12 y12 21 y21 13 y13 31 y31 23 y23 32 y32
一般化的Node-Link模型
min
( m , n )E

mn ymn
( i , n )E

ij xin
( m ,i )E

ij xin hij , i, j D
限制条件
要求每个业务只能在一条路径上传输或者 必须分在多条路径上传输
Routing Restrictions（多路径限制）
网络中由于流量均衡和生存性要求，所以 要求业务必须分配到多条路径上进行传输
要求传输的路径数目必须大于某个数值n
LP Formulation for Path Diversity Constraint（Multi-path)