This paper attends to the problem of embedding flexibly specified virtual networks connecting cloud resources (e.g., storage or computation) on a given substrate (e.g., a data center, an ISP backbone, a router site, or a virtual provider network). We study a scenario where a substrate provider (or a potential intermediate broker or reseller) wants to optimize the embedding of these so-called \CloudNets\ by migrating them to more suitable locations. For instance, such re-embeddings can be useful if the \CloudNets\ were requested at short notice and initially placed heuristically. Subsequent optimizations can, e.g., reduce the peak resource loads in the network by spreading \CloudNets\ across the infrastructure or save energy by moving \CloudNets\ together and switching off unused components. We present the generic mathematical programming algorithm used in our \CloudNet\ prototype to compute optimal embeddings. For example, this algorithm supports different objective functions (such as load minimization or energy conservation), arbitrary resource combinations and the mapping of multiple virtual nodes of a \CloudNet\ to a single substrate node, cost-aware migrations, and it can deal with all link types that arise in practice (e.g., full-duplex or even wireless or wired broadcast links with multiple endpoints). Of course, such rigorous \CloudNet\ optimizations are time consuming, and we report on the time complexities obtained from our experiments with our network virtualization prototype architecture. It turns out that optimizing \CloudNets\ over moderate sized infrastructures is feasible, even for scenarios with high flexibility and without tuning the solver software to speed up computations further.