readme

网络流量优化问题

给定一个网络G（V, E) ，其中V为节点集合，E为链路集合。网络中的每条链路e的容量为Ce拓扑上的数字为链路的容量，假设网络中有K条单向网络流（k=n*(n-1),n为网络节点的数目），假定第i条网络流为fi，流的大小从[10, 100]区间中随机产生。现需要对K条网络流进行合理的规划，以实现网络负载均衡的目标。假定网络负载均衡的指标为最小化最大链路利用率。代码实现内容如下

（1）采用Link-Path方式进行建模，并为每条流使用K路由算法计算3/5/7条备选路。

（2）采用求解器求解对偶模型 。

（3）比较原来模型和对偶模型的求解时间和优化目标值

对于上图未标明容量的链路，均假设其未500

说明

如需要自定网络G(V,E)，需修改prepare.py中的capacity_matrix ，即链路容量矩阵(对称阵且对角线全0)

以及main_cplex.py中的node_names ，如果修改需先按运行方法中的2进行

随机流大小以及随机权重均可在prepare.py中修改

运行方法

1. 运行main_cplex.py

终端输出

备选路径数量为7时
原始模型求解时间为5.9183ms
最小化最大值:12.12%
Graph saved at data/cplex_optimized_loadrate.png
对偶模型求解时间为9.9852ms
对偶模型最优值:12.12%

求解结束，并将求解后网络中各路径链路利用率生成为图片存储为data/cplex_optimized_loadrate.png

并导出原始模型和对偶模型的lp文件

2. 如需修改备选路径数或重新生成网络流和权重

2.1. 运行prepare.py

终端输出

是否重新生成网络流和链路权重(y/n):

输入y则重新生成随机大小的网络流和各链路权重

输入n则使用./data中weighted.pkl、random_flow.pkl等文件存储的数据，仅重新生成k条备选路径

终端输出

备选路径数量(3/5/7):

输入需要生成的备选路经数量后等待代码运行

终端输出

--already prepared--

表示prepare.py运行完毕

2.2. 再次运行main_cplex.py