The Internet has ossified. It has lost its capability to adapt as requirements change. A fitting practical example for ossification is the introduction of IPv6. It has been specified in 1998 to solve, among other things, the forseeable Internet address shortage. The addresses have begun to run out in 2011 and still IPv6 does not see any wide-spread usage; hacks like network address translation reduce the need to switch. A promising approach for solving this problem is the introduction of network virtualization. Instead of directly using the single physical network, unchangeable to a large degree and working just well enough for a limited range of applications, multiple virtual networks are embedded on demand into the physical network, each of them perfectly adapted to a specific application class. Compute capabilities within the network are provided to the virtual networks, enabling them to offer their own customized topologies, routing, resource management and naming services. There are still numerous unsolved problems regarding network virtualization, ranging from the implementation of virtualizable routers to economic aspects. In this thesis, we focus on the problem of resource allocation. All virtual networks, with all the resources they require (e.g., bandwidth), still need to fit into the available physical network. Our aim is not merely finding an arbitrary solution, we want to fit the virtual networks in a cost-optimal way. This is the core of the Virtual Network Mapping Problem (VNMP), an NP-complete Combinatorial Optimization Problem. We present several heuristic and exact approaches for solving the VNMP. As heuristic methods we investigate Construction Heuristics, Local Search, Variable Neighborhood Descent, Memetic Algorithms, Greedy Randomized Adaptive Search Procedures, and Variable Neighborhood Search. The exact approaches we develop are based on Constraint Programming and Integer Linear Programming. In addition to analyzing different solution methods and comparing their various strengths and weaknesses, we present a strong preprocessing method for VNMP instances. This preprocessing method can determine which parts of the physical network each virtual network can and cannot use. We show that preprocessing is essential for solving large VNMP instances with exact methods. For finding a valid mapping of virtual networks into substrate networks, the preprocessing method is powerful enough to make Integer Linear Programming the solution method of choice. For low-cost solutions, the situation is more complex. Integer Linear Programming is the best method for small to medium instance sizes. If run-time is a concern, our Memetic Algorithm and Variable Neighborhood Search approaches can be used to great effect, achieving costs within 5\% of the exact method. For large instances, we conclude that Variable Neighborhood Descent performs best.