.png){kind=icon}
返回
Benders decomposition for a node-capacitated Virtual Network Function placement and routing problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2021.105227.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this paper we study a problem faced by network service providers in which a set of Virtual Network Functions (VNFs) has to be installed in a telecommunication network at minimum cost. For each given origin-destination pair of nodes (commodities), a latency-constrained routing path has to be found that visits the required VNFs in a pre-defined order. A limited number of functions can be installed at each node. We first prove that the problem is NP-hard in a strong sense, even for a single commodity and without node-capacity, latency and precedence constraints. We then provide a compact Mixed Integer Linear Programming (MILP) formulation, along with several families of valid inequalities. To tackle the problem from a computational perspective, we provide theoretical results that allow us to derive Benders reformulation of the problem. We also exploit an alternative path-based MILP formulation to derive heuristic solutions. All these ingredients are combined in a Branch-and-Benders-Cut framework and computationally tested on a wide range of realistic instances. Our results are also compared with the Automatic Benders decomposition provided by Cplex. Computational results indicate that our decomposition approach is more efficient compared to the two methods provided by the off-the-shelf solver, both in terms of the CPU time and the overall solution quality. The results also indicate that our MILPheuristic provides high-quality solutions. (c) 2021 Elsevier Ltd. All rights reserved.
Keyword:
Combinatorial optimization
Benders decomposition
Software defined networking
Network Function Virtualization
Service function chaining
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
Joint Optimization of Service Function Chaining and Resource Allocation in Network Function Virtualization网络功能虚拟化中服务功能链与资源分配的联合优化.png)
IEEE ACCESSOAAI
IEEE ACCESSIF3.6
OAAI分享收藏Benders decomposition without separability: A computational study for capacitated facility location problems无可分离性的弯曲器分解: 针对容量限制的设施位置问题的计算研究
PREAI
分享收藏Benders decomposition for very large scale partial set covering and maximal covering location problems超大规模部分集合覆盖和最大覆盖位置问题的Benders分解OAAI
OAAI分享收藏
查看更多内容