Cloud computing services are very popular nowadays, because using these is beneficial for several reasons. The users can acquire a complete infrastructure with a few clicks, which consists of virtual machines hosted by the provider. Setting up and maintaining these computers is of absolutely no concern to the user.
The abstraction of resources makes it possible for the providers to share their physical machines among users. Multiple virtual machines - not necessarily from the same user - can be concurrently mapped to one physical machine.
The virtual machine allocation problem concerns how the provider should divide the capacity of its physical machines among the users, so that the operation costs are minimized. Recently, many solutions were proposed to this problem, most of which are based on some kind of mathematical programming or utilize simple heuristics.
In this thesis I propose a new method: a branch-and-bound algorithm tailored specifically for the virtual machine allocation problem. This algorithm merges the benefits of both previously used approaches: it is able to evaluate the optimality of its own solutions, while also being scalable for large problems by using various heuristics.
In order to prove that the branch-and-bound algorithm is indeed very efficient, I compare its performance with two state-of-the-art integer linear programming solvers. In comparison to these software, the solutions provided by my algorithm have on average about 12% lower cost for large inputs.