On the Virtual Network Embedding polytope
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914259400654848 |
|---|---|
| author | Benhamiche, Amal Fouilhoux, Pierre Létocart, Lucas Perrot, Nancy Schneider, Alexis |
| author_facet | Benhamiche, Amal Fouilhoux, Pierre Létocart, Lucas Perrot, Nancy Schneider, Alexis |
| contents | We initiate the polyhedral study of the Virtual Network Embedding (VNE) problem, which arises in modern telecommunication networks. We propose new valid inequalities for the so-called flow formulation. We then prove, through a dedicated flow decomposition algorithm, that these inequalities characterize the VNE polytope in the case of an embedding of a virtual edge on a substrate path. Preliminary experiments show that the new inequalities propose promising speedups for MIP solvers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_11419 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Virtual Network Embedding polytope Benhamiche, Amal Fouilhoux, Pierre Létocart, Lucas Perrot, Nancy Schneider, Alexis Discrete Mathematics Optimization and Control We initiate the polyhedral study of the Virtual Network Embedding (VNE) problem, which arises in modern telecommunication networks. We propose new valid inequalities for the so-called flow formulation. We then prove, through a dedicated flow decomposition algorithm, that these inequalities characterize the VNE polytope in the case of an embedding of a virtual edge on a substrate path. Preliminary experiments show that the new inequalities propose promising speedups for MIP solvers. |
| title | On the Virtual Network Embedding polytope |
| topic | Discrete Mathematics Optimization and Control |
| url | https://arxiv.org/abs/2601.11419 |