We present an approach for deploying and subsequently managing a virtual network overlay, which is tailored to an end-user's request. Our approach combines a binary integer optimisation process to decide on the number and placement of virtual routers, and an autonomic network management system that subsequently manages the configuration of the running virtual network. High-level optimisation policies are used to guide the optimisation process to identify a virtual network that favours lower hosting costs or higher network quality (we use mean delays as a quality metric). Low-level deployment policies are generated and used to govern the deployment and management of the virtual networks. Our results indicate that the binary integer optimisation process produces a virtual network that has lower cost as compared to creating a network based on combined shortest paths.