vmpacking (vmp)

This library implements algorithms for the VM Packing problem as part of my St Andrews Undergraduate Dissertation. Even though the dissertation has been submitted as of 4 April 2025, this repository is under development. I hope to continue providing implementations of more algorithms as they come up.

Approximations currently :

• Next Fit
• First Fit
• Greedy Placement by Efficiency
• Greedy Placement by Opportunity-Aware Efficiency
• Tree-Based Placement
• Overload and Remove
• Greedy Placement by Subset Efficiency (Reduction from VM Maximisation)
• Cluster Tree-Based Placement (Reduction from VM Maximisation)

All as credited in the relevant code.

Static treatments:

• Tree-/Cluster Tree-Ordering pre-treatment
• Decanting post-treatment

Build Instructions

Before building, please make sure your toolchain supports the following:

• CMake 3.14 or newer
• C++ 20 support, including std::ranges

Begin by cloning the repository:

git clone https://github.com/smich42/vmpacking.git
cd vmpacking

Create a build directory:

mkdir -p build && cd build

Configure the project (Release or Debug):

cmake .. -DCMAKE_BUILD_TYPE=Release

Build the project:

cmake --build .

TODOs

• (Priority) GuestSelection(size_t, const std::vector<std::shared_ptr<const Guest>> &) copies the guest vector. As this is an intermediate step in the Cluster Tree maximisation algorithm, it likely degrades performance substantially. Store only the selection mask for each cluster, and backtrack to reconstruct the guest vector.

• Add simple hand-traced cases as unit tests.

• Refactor the parsers for clarity

• Enforce invariants by design in the tree and cluster-tree models