A decomposition approach for large virtual network embedding
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "A decomposition approach for large virtual network embedding".
Jane: Here's the gist of the paper. Virtual Network Embedding (VNE) is the core combinatorial problem of Network Slicing, a 5G technology which enables telecommunication operators to propose diverse service-dedicated virtual networks, embedded onto a common substrate network On a benchmark of large virtual networks with realistic topologies we compiled, the state-of-the art heuristics often provide expensive solutions, or even fail to find a solution when resources are sparse We introduce a new integer linear formulation together with a decomposition scheme based on an automatic partition of the virtual network This results in a column generation approach whose pricing problems are also VNE problems Finally, we devise an efficient Price-and-Branch heuristic for large instances.
Tom: Problem Definition and Formulation The Virtual Network Embedding Problem (VNE) is defined as finding a minimum cost embedding of a virtual network Gr on a substrate network Gs A mapping m = (mV, mE) of Gr on Gs is a pair of functions where mV: Vr → Vs is called the node placement and mE: Er → Ps, is called the edge routing The VNE can be formulated as finding the minimum cost embedding of Gr on Gs given demands d, capacities c, and costs w.
Jane: Decomposition Strategy The authors propose a decomposition approach based on an automatic partition of the virtual network to tackle large instances The main contributions include introducing the Virtual Partition Formulation, an integer linear formulation based on a tuned partition of the virtual network.
Tom: This approach allows to compute better lower bounds than state-of-the-art methods.
Title and authors: Jane: So we've talked about the title and authors, but let's really unpack what this paper, "A decomposition approach for large virtual network embedding," is trying to achieve in its core summary. What’s the actual problem they are solving?
Tom: They are focusing on Virtual Network Embedding, VNE, which is that minimum cost mapping of a virtual network onto a substrate network that involves both node placement and edge routing decisions <ref:2512.17414#pg1>. It's the central combinatorial problem for resource allocation in network slicing <ref:2512.17414#pg3>.
Lu: The paper sets up the VNE as finding a minimum cost embedding of a virtual network Gr on a substrate network Gs, given demands, capacities, and costs <ref:2512.17414#pg3>. It defines the mapping as two functions: one for node placement and one for edge routing <ref:2512.17414#pg3>.
Jane: And they immediately point out that this VNE problem is known to be NP-complete, even with simpler constraints like uniform demands and topological restrictions <ref:2512.17414#pg3>. This sets the stage for why we need a smarter approach than just brute force.
Tom: Their main contribution is introducing the Virtual Partition Formulation, which they build on a tuned partition of the virtual network, and this leads to an integer linear formulation <ref:2512.17414#pg3>.
Meng: So it's taking that NP-complete problem and turning it into something solvable using integer linear programming by breaking it down based on that partition structure <ref:2512.17414#pg3>. That sounds like a big shift in methodology.
Jane: Right, and this decomposition allows them to compute much better lower bounds because they can use a column generation approach, where the pricing problems are also VNE problems on smaller virtual subgraphs <ref:2512.17414#pg3>.
Lu: And this is key because it means that instead of just solving one huge problem, you can solve many smaller VNE problems iteratively to get a better estimate <ref:2512.17414#pg3>.
Tom: They also detail how they use these pricing problems to compute Lagrangian bounds, which are strong lower bounds using the virtual network's structure <ref:2512.17414#pg3>.
Jane: And finally, they put all this together with a heuristic called Price-and-Branch that uses column generation to find the actual embedding solution for large instances <ref:2512.17414#pg3>.
Meng: So in simple terms, it’s about using structured decomposition to turn a very hard mapping problem into a series of solvable subproblems, helping you get both a good estimate and an actual answer.
Tom: That’s the essence of the paper: structure the problem to make solving it tractable by breaking down the complexity <ref:2512.17414#pg3>.
Jane: And they show that this structured approach, combined with their heuristic refinement, yields results that are significantly better than what we see from state-of-the-art algorithms <ref:2512.17414#pg3>.
The paper's summary: Lu: Let's focus on the specific ways they improved the existing methods, because I want to know what the paper actually suggests that is new and better than what we already have in the literature <ref:2512.17414#pg3>.
Tom: The first major improvement is introducing the Virtual Partition Formulation itself, which is based on a tuned partition of the virtual network, and this formulation allows them to compute better lower bounds compared to previous methods <ref:2512.17414#pg3>.
Jane: So it’s not just a new way to state the problem; it's a fundamentally different way to model the constraints on node placement and routing <ref:2512.17414#pg3>.
Lu: Then they introduce the decomposition scheme, which allows them to compute better lower bounds by using column generation where their pricing problems are VNE problems on smaller virtual subgraphs <ref:2512.17414#pg3>.
Meng: What about the heuristic refinement? Is there something specific in that Price-and-Branch heuristic that is new, or are we just seeing an application of existing techniques applied differently?
Tom: The improvement there is that they identified issues in the columns produced by their procedure and proposed algorithmic fixes, specifically partitioning the substrate network into balanced subgraphs one <ref:2512.17414#pg2>.
Jane: And they also propose modifying the objective functions of those sub-pricers to incorporate an estimation of routing costs for edges that cross between these virtual cuts one <ref:2512.17414#pg2>.
Lu: This modification is clever because it helps ensure that the columns generated on a subgraph don't intersect with all the columns from other subgraphs, which makes the generation process much more efficient one <ref:2512.17414#pg2>.
Tom: So they are essentially making sure that their decomposition works well practically, not just theoretically, by tuning those structural parameters based on where they see bottlenecks in column production one <ref:2512.17414#pg2>.
Jane: It sounds like they moved beyond just a mathematical formulation and into the practical engineering of how to make the search process actually work efficiently for large instances.
The paper's improvements: Tom: So wrapping up this paper, the main takeaway is that by using a decomposition approach based on partitioning both networks, they can achieve better lower bounds and then use an efficient Price-and-Branch heuristic to find high-quality solutions for large virtual network embedding instances <ref:2512.17414#pg3>.
Jane: This structured method lets them get a good estimate early on, and then the refinement helps them actually land on a solution that is much better than what we have in the literature <ref:2512.17414#pg3>.
Lu: It’s about getting that trade-off between how much you partition versus how efficient those pricing problems end up being, which is a core insight here <ref:2512.17414#pg3>.
Meng: From an operational standpoint, the fact that this heuristic outperforms algorithms on large instances of the Internet Topology Zoo and SNDlib is good, especially with tight capacities where greedy approaches fail <ref:2512.17414#pg3>.
Tom: Yeah, so they developed a new integer linear programming formulation for VNE based on network partitioning and then an automatic decomposition scheme that lets you get better bounds before using their Price-and-Branch heuristic for large instances <ref:2512.17414#pg3>.
Jane: It really gives us a solid tool to think about how to handle those massive resource allocation problems in future network designs <ref:2512.17414#pg3>.
Lu: The next step is seeing if this decomposition strategy holds up when we move beyond these benchmark instances and into much more complex, real-world topologies <ref:2512.17414#pg3>.
Meng: I'm still focused on the deployment cost aspect, but for now, this paper shows a path forward for handling these large VNE problems systematically <ref:2512.17414#pg3>.
Conclusion: Tom: So we've seen how they took Virtual Network Embedding, VNE, which is that hard mapping problem for 5G networks, and they introduced this new integer linear formulation based on partitioning the virtual network <ref:2512.17414#pg3>.
Jane: Exactly. The naive question a listener might have is how do you even start modeling all that placement and routing simultaneously? And they tackle that by introducing this partition structure <ref:2512.17414#pg3>.
Lu: It’s a decomposition approach. They take the big virtual network, break it down into smaller parts, and solve the embedding problem on those pieces <ref:2512.17414#pg3>.
Meng: So what does that actually mean for me running things at scale? Does breaking it down make the computation faster or just more complex to set up?
Tom: It's supposed to let them compute much better lower bounds, which is a big deal because those bounds are usually weak with standard approaches <ref:2512.17414#pg3>.
Jane: They use column generation for this decomposition, and the pricing problems are actually smaller VNE problems themselves <ref:2512.17414#pg3>. That means they can get stronger estimates iteratively <ref:2512.17414#pg3>.
Lu: And then they refine their heuristic, the Price-and-Branch method, by partitioning the substrate network into balanced subgraphs <ref:2512.17414#pg3>. They also adjust the objective functions of those sub-pricers to estimate routing costs for edges crossing between those cuts <ref:2512.17414#pg3>.
Meng: If you’re shipping models, that sounds like it adds a lot of overhead in terms of setup time, but if it helps you get a feasible solution faster on large instances, I can see that <ref:2512.17414#pg3>.
Tom: And the results show this heuristic beats the state-of-the-art algorithms on all solved instances <ref:2512.17414#pg3>. They found solutions for instances up to one hundred nodes in their tests <ref:2512.17414#pg3>.
Jane: It’s really a big step because before this, greedy approaches just couldn't solve the tight capacity instances correctly <ref:2512.17414#pg3>. This paper shows how structure helps you find those better embeddings <ref:2512.17414#pg3>.
Lu: The main point is that they created a new integer linear programming formulation for Virtual Network Embedding, based on network partitioning, and an automatic decomposition scheme that balances the partition size with pricing problem efficiency <ref:2512.17414#pg3>.
Meng: So it’s not just a theoretical improvement; it’s practical because they devised a way to get actual solutions for massive virtual networks, which is what I need to deploy things reliably <ref:2512.17414#pg3>.
Tom: It really is about structuring the problem so that you get better bounds first and then you have an efficient heuristic to find the actual embedding, which means we can actually build these virtual networks <ref:2512.17414#pg3>.
Jane: This work shows a clear path for how we can handle these huge resource allocation problems in future network designs <ref:2512.17414#pg3>.
Tom: That’s it for today on "A decomposition approach for large virtual network embedding". Next week, we’re looking at how LLM coding agents are using test generation to improve their performance <ref:2512.17414#pg56>
Amal Benhamiche, Pierre Fouilhoux, Lucas Létocart, Nancy Perrot, Alexis Schneider
Orange Research · Laboratoire d’Informatique de Paris Nord, LIPN, CNRS
cs.DM, cs.NI
Submitted: 2025-12-19
Updated: 2026-11-09
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 75/100
The gist: Virtual Network Embedding (VNE) is the core combinatorial problem of Network Slicing, a 5G technology which enables telecommunication operators to propose diverse service-dedicated virtual networks…
Key concepts
- Virtual Network Embedding (VNE)
- VNE is the core problem of 5G network slicing, which is finding the minimum cost way to place virtual network nodes and route virtual edges onto a shared physical substrate network. It determines how a desired service can be realized using existing infrastructure.
- Integer Linear Formulation (ILF)
- This is a mathematical model used to define the VNE problem precisely, ensuring that all decisions—like where to place nodes and how to route edges—are represented by integer variables. This formulation is crucial for creating strong lower bounds and guiding the optimization process.
- Column Generation
- This is an algorithmic technique used to solve large optimization problems by iteratively generating only the most promising solutions (columns) rather than checking every possibility. In this context, it helps find good lower bounds by solving pricing problems that are themselves VNE subproblems.
Terminology
Summary
Virtual Network Embedding (VNE) is the core combinatorial problem of Network Slicing, a 5G technology which enables telecommunication operators to propose diverse service-dedicated virtual networks, embedded onto a common substrate network On a benchmark of large virtual networks with realistic topologies we compiled, the state-of-the art heuristics often provide expensive solutions, or even fail to find a solution when resources are sparse We introduce a new integer linear formulation together with a decomposition scheme based on an automatic partition of the virtual network This results in a column generation approach whose pricing problems are also VNE problems Finally, we devise an efficient Price-and-Branch heuristic for large instances. p. 0 p. 0
Problem Definition and Formulation
The Virtual Network Embedding Problem (VNE) is defined as finding a minimum cost embedding of a virtual network Gr on a substrate network Gs A mapping m = (mV, mE) of Gr on Gs is a pair of functions where mV: Vr → Vs is called the node placement and mE: Er → Ps, is called the edge routing The VNE can be formulated as finding the minimum cost embedding of Gr on Gs given demands d, capacities c, and costs w.
Decomposition Strategy
The authors propose a decomposition approach based on an automatic partition of the virtual network to tackle large instances The main contributions include introducing the Virtual Partition Formulation, an integer linear formulation based on a tuned partition of the virtual network. This approach allows to compute better lower bounds than state-of-the-art methods. p. 0
Column Generation and Lower Bounds
The paper describes a column generation implementation to solve the linear relaxation of the Virtual Partition Formulation (V P F) and compute strong lower bounds The pricing problem P Pi is actually a VNE problem of the virtual subgraph Hi r on Gs. A Lagrangian bound LGB = v(RMP) + X i∈[kr] v∗ (P Pi) (4) is computed at each step of the algorithm. p. 8
Heuristic Refinements
The authors devise a Price-and-Branch heuristic that outperforms state-of-the-art algorithms They identify issues in columns produced using the procedure in Section 4 and propose algorithmic improvements to correct these issues. Specifically, they suggest partitioning the substrate network into balanced subgraphs whose average size is about 1. p. 85 times the maximum size of the virtual subgraphs. p. 8 They also propose modifying the objective functions of the sub-pricers to incorporate an estimation of routing costs for virtual cut edges. p. 4
Performance Evaluation
The results show that the new Virtual Partition Formulation is much stronger than the Flow Formulation The Price-and-Branch heuristic outperforms state-of-the-art algorithms on all solved instances. For large capacities, every node placement leads to a feasible solution, and the heuristic finds significantly better embeddings than baselines. p. 4 The best solutions are found with kr = ⌊ nr/10 ⌋ and kr = ⌊ nr/10 ⌋ + 1. p. 2
Conclusion
This paper introduces a new integer linear programming formulation for Virtual Network Embedding, based on a partition of the virtual network We propose an automatic decomposition scheme that allows a good trade-off between the size of the partition and the efficiency of the pricing problems. p. 0 A first column generation approach using dedicated heuristic pricers is able to compute better lower bounds than state-of-the-art methods In the aim of producing solutions, we identified some column structures and devised a Price-and-Branch heuristic that obtains solutions for instances with large virtual networks, up to 110 nodes in our tests. p. 0 This heuristic outperforms the algorithms from the literature for large instances of the Internet Topology Zoo and SNDlib, in particular with tight capacities instances, while greedy approaches fail to solve them. p. 3 The paper introduces a new integer linear programming formulation for Virtual Network Embedding, based on a partition of the virtual network. p. 0 We propose an automatic decomposition scheme that allows a good trade-off between the size of the partition and the efficiency of the pricing problems. A first column generation approach using dedicated heuristic pricers is able to compute better lower bounds than state-of-the-art methods. p. 0 Finally, we devise an efficient Price-and-Branch heuristic for large instances.
References
[1] Thomas Anderson, Larry Peterson, Scott Shenker, and Jonathan Turner. Overcoming the internet impasse through virtualization [2] Jonathan S Turner and David E Taylor. p. 0 Diversifying the internet. p. 0 In GLOBECOM’05 [3] NM Mosharaf Kabir Chowdhury and Raouf Boutaba. A survey of network virtualization [4] NGMN Alliance. p. 0 Description of network slicing concept [5] 3rd Generation Partnership Project. p. 0 5g; management and orchestration; concepts, use cases and requirements, release 15 [6] Xenofon Foukas, Georgios Patounas, Ahmed Elmokashfi, and Mahesh K Marina. Network slicing in 5g: Survey and challenges [7] Jose Ordonez-Lucena, Pablo Ameigeiras, Diego Lopez, Juan J Ramos-Munoz, Javier Lorca, and Jesus Folgueira. Network slicing for 5g with sdn/nfv: Concepts, architectures, and challenges [8] Ibrahim Afolabi, Tarik Taleb, Konstantinos Samdanis, Adlen Ksentini, and Hannu Flinck. p. 3 Network slicing and softwarization: A survey on principles, enabling technologies, and solutions [9] T-Mobile. p. 1 America’s best 5g network experience for first responders, 2025 [10] Siemens. p. 1 Siemens and o2 telefónica partner to develop solutions based on 5g network slicing, 2025 [11] Jing Lu and Jonathan Turner. p. 1 Efficient mapping of virtual networks onto a shared substrate [12] Y. p. 0 Zhu and M. Ammar. Algorithms for assigning substrate network resources to virtual network components [13] Spyridon Vassilaras, Lazaros Gkatzikis, Nikolaos Liakopoulos, Ioannis N Stiakogiannakis, Meiyu Qi, Lei Shi, Liu Liu, Merouane Debbah, and Georgios S Paschos. p. 0 The algorithmic aspects of network slicing [14] Edoardo Amaldi, Stefano Coniglio, Arie MCA Koster, and Martin Tieves. p. 3 On the computational complexity of the virtual network embedding problem [15] Matthias Rost and Stefan Schmid. p. 0 On the hardness and inapproximability of virtual network embeddings [16] Amal Benhamiche, Pierre Fouilhoux, Lucas Létocart, Nancy Perrot, and Alexis Schneider. p. 0 Complexity of the virtual network embedding with uniform demands [17] Matthias Rost, Carlo Fuerst, and Stefan Schmid. p. 2 Beyond the stars: Revisiting virtual cluster embeddings [18] Andreas Fischer, Juan Felipe Botero, Michael Till Beck, Hermann De Meer, and Xavier Hesselbach. p. 5 Virtual network embedding: A survey [19] Mosharaf Chowdhury, Muntasir Raihan Rahman, and Raouf Boutaba. p. 2 Vineyard: Virtual network embedding algorithms with coordinated node and link mapping [20] Minlan Yu, Yung Yi, Jennifer Rexford, and Mung Chiang. p. 0 Rethinking virtual network embedding: Substrate support for path splitting and migration [21] Xiang Cheng, Sen Su, Zhongbao Zhang, Hanchi Wang, Fangchun Yang, Yan Luo, and Jie Wang. p. 2 Virtual network embedding through topology-aware node ranking [22] Long Gong, Yonggang Wen, Zuqing Zhu, and Tony Lee. p. 3 Toward profit-seeking virtual network embedding algorithm via global resource capacity [23] Peiying Zhang, Haipeng Yao, and Yunjie Liu. p. 2 Virtual network embedding based on the degree and clustering coefficient information [24] Johannes Inführ and Günther R Raidl. p. 2 Solving the virtual network mapping problem with construction heuristics, local search and variable neighborhood descent [25] Amine Rguez, Yassine Hadjadj-Aoul, and Gerardo Rubino. p. 2 A grasp-based approach for dynamic and reliable virtual network embedding [26] Zhongbao Zhang, Xiang Cheng, Sen Su, Yiwen Wang, Kai Shuang, and Yan Luo. p. 2 A unified enhanced particle swarm optimization-based virtual network embedding algorithm [27] Peiying Zhang, Yanrong Hong, Xue Pang, and Chunxiao Jiang. p. 2 Vne-hpso: Virtual network embedding algorithm based on hybrid particle swarm optimization [28] Ilhem Fajjari, Nadjib Aitsaadi, Guy Pujolle, and Hubert Zimmermann. p. 2 Vne-ac: Virtual network embedding algorithm based on ant colony metaheuristic [29] Peiying Zhang, Haipeng Yao, Maozhen Li, and Yunjie Liu. p. 2 Virtual network embedding based on modified genetic algorithm [30] Xu Liu, Zhongbao Zhang, Ximing Li, and Sen Su. p. 2 Optimal virtual network embedding based on artificial bee colony [31] Fangjin Zhu and Hua Wang. p. 4 A modified aco algorithm for virtual network embedding based on graph decomposition [32] An Song, Wei-Neng Chen, Yue-Jiao Gong, Xiaonan Luo, and Jun Zhang. p. 2 A divide-and-conquer evolutionary algorithm for large-scale virtual network embedding [33] Soroush Haeri and Ljiljana Trajkovic. p. 2 Virtual network embedding via monte carlo tree search [38] NM Mosharaf Kabir Chowdhury, Muntasir Raihan Rahman, and Raouf Boutaba. p. 2 Virtual network embedding with coordinated node and link mapping [39] Marcio Melo, Susana Sargento, Ulrich Killat, Andreas Timm-Giel, and Jorge Carapinha. p. 0 Optimal virtual network embedding: Node-link formulation [40] Leonardo FS Moura, Luciano P Gaspary, and Luciana S Buriol. p. 4 A branch-and-price algorithm for the single-path virtual network embedding problem [41] Matthias Rost and Stefan Schmid. p. 2 Virtual network embedding approximations: Leveraging randomized rounding [42] Rashid Mijumbi, Joan Serrat, Juan-Luis Gorricho, and Raouf Boutaba. p. 2 A path generation approach to embedding of virtual networks [43] Abdallah Jarray and Ahmed Karmouch. p. 2 Decomposition approaches for virtual network embedding with one-shot node and link mapping [46] Alexis Schneider. p. 0 Vne lib: a library for offline virtual network embedding instances, 2021 [48] Simon Knight, Hung X Nguyen, Nickolas Falkner, Rhys Bowden, and Matthew Roughan. p. 3 The internet topology zoo [49] Sebastian Orlowski, Roland Wessäly, Michal Pióro, and Artur Tomaszewski. p. 3 Sndlib 1.0—survivable network design library [50] Wesley da Silva Coelho, Amal Benhamiche, Nancy Perrot, and Stefano Secci. p. 3 On the impact of novel function mappings, sharing policies, and split settings in network slice design [58] Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral B Shah. p. 3 Julia: A fresh approach to numerical computing [59] James Fairbanks, Mathieu Besançon, Schölly Simon, Júlio Hoffiman, Nick Eubank, and Stefan Karpinski. Juliagraphs/graphs. p. 1jl: an optimized graphs package for the julia programming language [60] Iain Dunning, Joey Huchette, and Miles Lubin. p. 9 Jump: A modeling language for mathematical optimization [63] Robert W Floyd. p. 3 Algorithm 97: shortest path
Table 3
| Capacities | Large | Medium | Small |
|---|---|---|---|
| IRIS | 180.6 | 207.0 | 180.8 |
| zib54 TATA | 225.219364564564564564563993739937399371880 |
| Hibernia 222.4 | 0.0 | 0.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Decomposition approach for Virtual Network Embedding: The system can compute better lower bounds than state-of-the-art methods by introducing a new integer linear formulation based on an automatic partition of the virtual network, allowing for a column generation approach whose pricing problems are also VNE problems.
-
Price-and-Branch heuristic refinement: The improved heuristic can find high quality solutions for large virtual networks by using an efficient Price-and-Branch heuristic that incorporates routing cost estimations through Algorithm 2, which adjusts placement costs based on the shortest path distance to temporary placements in other substrate subgraphs.
-
Substrate network partitioning for pricing: The system can generate columns more efficiently by partitioning the substrate network into balanced subgraphs and generating sub-pricers on these parts, ensuring that
Columns generated on a substrate subgraph do not intersect with all columns from other substrate subgraphs.
Sources
Related papers
- Low-Temperature Sampling via Equilibrium Disagreements
- An Improved Bound for Testing k-Colorability
- Temporal Cliques Admit Linear Spanners
- Multiway Partition is FPT for Connectivity Functions
- Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
- Constrained intersection representations and forbidden patterns