The Virtual Network Embedding Problem (VNEP) captures the essence of many resource allocation problems of today’s infrastructure providers, which offer their physical computation and networking resources to customers. Customers request resources in the form of Virtual Networks, i.e. as a directed graph which specifies computational requirements at the nodes and communication requirements on the edges. An embedding of a Virtual Network on the shared physical infrastructure is the joint mapping of (virtual) nodes to physical servers together with the mapping of (virtual) edges onto paths in the physical network connecting the respective servers.This work initiates the study of approximation algorithms for the VNEP. Concretely, we study the offline setting with admission control: given multiple request graphs the task is to embed the most profitable subset while not exceeding resource capacities. Our approximation is based on the randomized rounding of Linear Programming (LP) solutions. Interestingly, we uncover that the standard LP formulation exhibits an inherent structural deficit when considering general virtual networks: its solutions cannot be decomposed into valid embeddings. In turn, focusing on the class of cactus request graphs, we devise a novel LP formulation, whose solutions can be decomposed into convex combinations of valid embedding. Proving performance guarantees of our rounding scheme, we obtain the first approximation algorithm for the VNEP in the resource augmentation model.We propose two rounding heuristics and evaluate their performance in an extensive computational study, showing that these consistently yield good solutions (even without augmentations).
A column generation approach was proposed by in @cite_2 to efficiently compute solutions to the VNEP by generating feasible mappings on-the-fly subject to a specific cost measure. In particular, compute feasible mappings by relying on heuristics and, if no feasible heuristical solution was found, rely on Mixed-Integer Programming to compute a cost optimal feasible embedding in non-polynomial time. We believe that our work can bridge the gap between the heuristic generation of feasible mappings and the optimal generation of feasible mappings as our approach can be used to compute mappings.
@cite_2
2038021311
This paper studies a routing problem in a multimodal network with shipment consolidation options. A freight forwarder can use a mix of flexible-time and scheduled transportation services. Time windows are a prominent aspect of the problem. For instance, they are used to model opening hours of the terminals, as well as pickup and delivery time slots. The various features of the problem can be described as elements of a digraph and their integration leads to a holistic graph representation. This allows an origin- destination integer multi-commodity flow formulation with non-convex piecewise linear costs, time windows, and side constraints. Column generation algorithms are designed to compute lower bounds. These column generation algorithms are also embedded within heuristics aimed at finding feasible integer solutions. Computational results with real-life data are presented and show the efficacy of the proposed approach.