The increased flexibility and inter-connectivity of modern industrial communication networks, obtained through the use of innovative technologies like Network Function Virtualization (NFV) and Software Defined Networking (SDN), requires a secure and manageable framework to support the new communication and computing needs. To focus on these requirements, this paper proposes a framework for reliable placement of services across physically separated locations, which offers both system optimization, in terms of latency and resource utilization, and connectivity policy enforcement to guarantee service reliability, safety, and security. This is achieved by exploiting a new approach to solve the virtual network embedding problem, using Optimization Modulo Theories (MaxSMT), which allows the use of very expressive constraints.