\myheading{Packing virtual machines into servers}
\label{VM_packing}

\renewcommand{\CURPATH}{knapsack/VM_packing}

You've got these servers (all in GBs):

% FIXME: table
\begin{lstlisting}
     RAM storage
 srv0  2     100
 srv1  4     800
 srv2  4    1000
 srv3 16    8000
 srv4  8    3000
 srv5 16    6000
 srv6 16    4000
 srv7 32    2000
 srv8  8    1000
 srv9 16   10000
srv10  8    1000
\end{lstlisting}

And you're going to put these virtual machines to servers:

\begin{lstlisting}
    RAM storage
 VM0  1     100
 VM1 16     900
 VM2  4     710
 VM3  2     800
 VM4  4    7000
 VM5  8    4000
 VM6  2     800
 VM7  4    2500
 VM8 16     450
 VM9 16    3700
VM10 12    1300
\end{lstlisting}

The problem: use as small number of servers, as possible.
Fit VMs into them in the most efficient way, so that the free RAM/storage would be minimal.

This is like knapsack problem.
But the classic knapsack problem is about only one dimension (weight or size).
We've two dimensions here: RAM and storage.
This is called \emph{multidimensional knapsack problem}.

Another problem we will solve here is a \emph{bin packing problem}.

\lstinputlisting[style=custompy]{\CURPATH/VM_pack.py}

( \url{\RepoURL/\CURPATH/VM_pack.py} )

The result:

\lstinputlisting{\CURPATH/result.txt}

Choose any solution you like...

Further work: storage can be both HDD and/or SDD. That would add 3rd dimension. Or maybe number of CPU cores, network bandwidth, etc...