限制性通信网络扩容问题研究

本研究针对通信网络运营商所面临的通信业务量迅速增大、网络容量和质量压力巨大的问题，希望通过与上海理想信息产业有限公司的合作共同探讨在现有的通信网络条件下，研究如何对电信网络中的弧（或边）进行扩容以满足急速增长的用户数量的需求。主要开展在子图为支撑树和路的情况下有约束限制的网络扩容问题的研究工作，为这两类限制扩容问题建立对应的组合优化模型，探讨其NP-完备性, 采用Lagrangean 松弛的方法将约束条件转化到目标函数中从而将约束问题转化为一个无约束规划问题并设计相应的近似算法；在此基础上研究这两类扩容问题的特殊形式，利用求解双权重优化问题的思路并为其设计多项式时间求解算法；进行通信网络实际案例计算机模拟，验证模型的合理性。预期发表与限制性网络扩容问题相关的高质量论文3篇，丰富组合优化限制性优化问题或双权重优化问题理论与算法，为通信网络运行商提供提供理论依据和解决方案。

《限制性通信网络扩容问题研究》是个一年期的资助项目，该研讨项目针对通信网络运营商所面临的通信业务量迅速增大、网络容量和质量压力巨大的问题，通过与中国电信上海理想信息产业（集团）有限公司的合作，共同探讨在现有的通信网络条件下，研究了如何对电信网络中的弧（或边）进行扩容以满足急速增长的用户数量的需求。通过一年的研究与合作，完成既定的研讨项目的内容，达到预期的研究目标。.项目的完成情况和取得成果：.1、项目组成员，上海理想信息产业李海荣高级工程师，来云南大学进行了为期一周的通信网络扩容问题的研究与探讨。李海荣站在现场和技术的角度探讨了我们的网络扩容问题的数学优化模型的可行性，并深入谈及到当前网络运行商在网络扩容方面所面临的一些实际技术、优化算法问题。从市场、技术、数学优化模型以及优化算法设计方面开拓我们目前的研究视野，也为下一步的研究方向提供了很好的问题背景和数学优化要求。.2、在美国内华达州参加Neural Information Processing Systems 2012国际会议一次，该会议多方面涉及到关于通信网络扩容方面所需的机器学习优化技术以及图论模型的建立与优化算法。.3、在前期的有约束限制的网络扩容问题的研究基础上，对限制性支撑树的扩容问题和限制性路的扩容问题，建立对应的组合优化模型，探讨其NP-完备性；在此基础上研究这两类扩容问题的特殊形式，利用求解双权重优化问题的思路并为其设计多项式时间算法。并在前期的限制性支撑树的扩容问题上进一步深化研究，探讨了邻接拟阵交变换算法。.4、研究了资源受限的最小支撑树形图的启发式算法，进行了大量的计算机模拟验证了启发式算法的合理性。支撑树树形图是我们将来通信网络扩容问题的一个方向。.5、已经完成关于通信网络扩容问题的数学优化论文3篇，3篇论文都已经投稿。.6、本年指导硕士研究生3名，1名正常毕业；项目组成员李海荣从工程师晋升为高级工程师。