Virtual Machine (VM) Allocation Problem (VMAP) is a resource allocation problem in virtualized cloud environments. This paper introduces a combinatorial auction based mathematical model for the VMAP. In this model, cloud users submit their complicated VM allocation requests to the cloud provider using the provided bidding language. The proposed model then selects the most profitable set of bids which can be mutually satisfiable while considering the mapping of the VMs to the physical computational resources. This mapping process is carried out so as to minimize the energy cost, thus providing an energy efficient solution to the VMAP. Two variants of the model are proposed: the static model and the dynamic model which are differentiated on how the computational resources are configured for VM execution. The proposed model is mathematically defined and the winner determination problems for the two variants are formulated using linear integer programming. A test case generator for the model is implemented and a comprehensive test suite is prepared. The performance of the model and its benefits in cloud environments in terms of energy efficiency are experimentally demonstrated on the prepared test suite.