The virtual network embedding (VNE) problem has been receiving significant research interest lately. A realistic scenario might entail embedding multiple VN requests (MVNE) that arrive simultaneously (batch arrivals). The existing MVNE approaches either did not consider the coordination among multiple VNR embeddings or embedded all the arriving VNRs simultaneously without considering the substrate network state. This paper considers the MVNE problem in the scenarios where the available physical resources may not be sufficient to satisfy the physical resource demands of all the VNRs in the batch. We formulate the problem as mixed integer programs, which not only provide optimal MVN embedding but also improve the network service provider's long-term revenue. Simulation results validate the revenue gains of the proposed approach over the existing exact and heuristic MVNE approaches.