k-可分流最小拥塞的算法研究

The only difference between the k-splittable flow multi-commodity transmission problem proposed by Baier in 2002 and the traditional multi-commodity transmission problem is that it restricts the number of paths each commodity can use, this transmission model can give a more centralized management of the commodity transmission of the whole network，which is a great breakthrough to the traditional multi-commodity transmission models. In order to balance the load of the network to severe more commodities, minimizing the congestion of the network is always one of the important objectives in network optimization problems, but the traditional multi-commodity transmission algorithms of minimizing congestion are not suitable for the k-splittable problem, hence the new algorithms are urgently needed to be proposed. This project mainly studies the k-splittable multi-commodity transmission problem with the objective of minimizing congestion, and we try to derive some innovative contributions from the following two aspects: On the one hand, by exploring the new methods and new techniques to improve the existing approximation algorithms in the literature, and design more higher universal approximation algorithms; On the other hand, in view of the characteristics of the k-splittable flow problem, we try to make some breakthroughs on the branch and price exact algorithm, on some key issues of the implementation of the algorithm, such as the initial feasible solution selection, the determination of column generation strategies and branching rules, we will give effective solutions, and test the algorithms by instance simulation.

Baier在2002年提出的k-可分流多商品传输问题，与传统多商品传输问题的唯一区别在于限制了每个商品传输可使用的路径数目，该传输模型可以对整个网络的商品传输进行更集中的管理，是对传统多商品传输模型的一个极大突破。为使得网络负载均衡以服务更多的商品，最小化网络拥塞一直是网络优化问题的重要研究目标之一，而传统的多商品传输最小拥塞算法已经不适用于k-可分流问题，亟需提出更新的算法。本项目主要研究目标为最小拥塞的k-可分流多商品传输问题，并力求在以下两个方面取得若干创新性成果：一、探索新方法和新技巧改进文献中关于该问题的近似算法，给出普适性较高的近似算法；二、针对k-可分流问题的特点，在分支定价精确算法设计方面力求有所突破，在算法执行过程中的几个关键问题上，如初始可行解的选取，列生成策略及分支准则的确定等，给出有效的求解方案，并对算法通过实例仿真进行验证。

随着通信网络的迅速发展，网络中多商品传输问题得到了广泛的研究，其中k-可分流多商品传输问题限制了每个商品传输请求量时可使用的路径数目，这一特点在很大程度上增强了网络的集中管理能力，使得网络维持在一个高效的运营状态。本项目对k-可分流多商品传输最小拥塞问题的算法设计进行深入的研究，主要从问题的复杂性分析，近似算法设计，精确算法设计，在线算法设计等方面进行研究，得到了一系列结果。受本项目资助共发表期刊学术论文10篇，其中SCI期刊论文6篇。代表性成果如下：(1)对多源多商品精确一致k-可分流最小拥塞问题，采用3-D matching NP-难问题归约的方法，证明得到拥塞值小于2的近似算法为NP-难问题；对于单商品k-可分流最小拥塞问题，采用SAT NP-难问题归约的方法，证明得到拥塞值小于1.618的近似算法为NP-难问题。(2)对于单源k-可分流最小拥塞问题，我们推广文献中所有商品传输路径数目为2的特殊情形到更一般的情形，得到了关于拥塞和费用的近似比。(3)对于精确算法，我们采用分支定价精确算法，给出了算法关键执行步骤的解决方案。(4)将在线多商品传输问题转化为一类在线排序问题，采用在线排序算法设计的技巧与思路，我们得到了丰富的结果。对某些问题给出了最优或最好可能的在线算法，并对某些问题给出了问题的下界。