● 摘要
在计算机网络中，网络服务提供商通常需要求解一个流量工程问题进而对当前网络的路由配置进行调整以优化网络性能．由于网络中转发节点数目的庞大，使得流量工程问题的规模也庞大，从而利用问题的特点设计高效算法是流量工程应用的前提．本文对最小化最大链路利用率和最小化M/M/1延迟费用函数逐段线性近似的流量工程问题(分别简称为MLU流量工程问题和FT流量工程问题)，做了以下几方面的工作． 首先以低存储需求为动机，利用Dantzig-Wolfe分解法求解两类流量工程问题．考虑到流量工程问题所具有的特殊的网络结构，可以在几方面对原始Dantzig-Wolfe分解法的求解效率进行提高．这包括利用网络单纯形法求解子问题，利用warm-start技术提高子问题求解效率，以及相关操作的简化计算．其次，对于FT流量工程问题，利用紧逆法开发基矩阵具有多个单位列的结构，并运用到Dantzig-Wolfe分算法中．基于该结构，我们设计出两种求解该问题的有效算法：固定维数的紧逆法，即迭代过程中工作基的维数保持不变，该方法利用了当前基中所含单位列数目的下界；变维数的紧逆法，即迭代过程中工作基的维数在相邻两次迭代有可能增加或降低一维，该方法精确利用了当前基中的这些单位列．固定维数的紧逆法虽然较可变维数的紧逆法在存储空间上没有充分节省，但是在实现时可以事先分配一个固定的存储空间，而可变维数的紧逆法虽然动态申请存储空间，但是其在存储空间上的进一步降低也是可观的，并且其维数的降低表明相关计算量小，这样在整个算法中计算效率得到进一步的提高．数值实验表明可变维数的紧逆法的求解效率优于固定维数的紧逆法．