论文标题
嵌套的列生成分解用于求解弹性光学网络中的路由和频谱分配问题
Nested Column Generation decomposition for solving the Routing and Spectrum Allocation problem in Elastic Optical Networks
论文作者
论文摘要
随着互联网流量的持续增长以及光谱的稀缺性，不断需要优化此资源的使用。在使用灵活频率网格范式配置弹性光网络的过程中，电信操作员必须处理NP完整的组合优化问题，即NP完整问题，即路由和频谱分配（RSA）问题。在我们先前的研究之后，我们使用了整数线性编程，并根据LightPath分解提出了一种列的生成算法，该算法被证明是迄今为止最有效的，我们现在考虑了过去在其他作品中研究的传统配置分解。在此过程中，我们使用两个变量集而不是单个变量集创建了一个新的数学模型。同样重要的是，我们独立地重新发现了嵌套的列的生成技术，并使用它提出了一种算法，从而导致了对使用相同配置分解的先前算法的可观改进。与最新的现有研究相比，我们的算法达到了1％的准确性差距，而先前的研究的准确性差距为14.3％，而运行时间平均要快两个数量级。
With the continued growth of Internet traffic, and the scarcity of the optical spectrum, there is a continuous need to optimize the usage of this resource. In the process of provisioning elastic optical networks using the flexible frequency grid paradigm, telecommunication operators must deal with a combinatorial optimization problem that is NP-complete namely the Routing and Spectrum Allocation(RSA) problem. Following on our previous study, where we used Integer Linear Programming, and proposed a Column Generation algorithm based on a Lightpath decomposition, which proved to be the most efficient so far, we now consider the traditional Configuration decomposition that has been studied in other works in the past. In the process, we created an new mathematical model using two variable sets instead of a single variable set. Equally important,we independently rediscovered the Nested Column Generation technique, and we used it to propose an algorithm that led to a considerable improvement on the previous algorithms that use the same Configuration decomposition. When compared to the latest such existing study, our algorithm achieved an accuracy gap of 1% as opposed to 14.3% for the previous study, and a running time two orders of magnitude faster on average.
