IMMC2023: How GPU and game development skills can help mathematical modeling

I participated in the International Mathematical Modeling Challenge of 2023 with a couple of my classmates. I was certain that my programming skills would come to use one way or the other.

For this year's competition, one of the tasks (Problem A) we had to do was to find the best use of the land, located near New York State. However we also had to consider things such as environmental impact, so simply removing the forests would not be the best option. 

We were able to find the land type data provided by the United States Geological Survey, in the form of a bit map. This allows us to model based on a 2-dimensional map. Our approach was to compute different indexes that determined how well specific building types fitted on different land types (e.g. constructing residential area on wetlands). Then, we use K-Means clustering to find the best solution. K-Means is done by randomly placing different building types onto the map, then for each pixel (a unit of land), we calculate the building with the highest score (distance, closer the better, and how well it fits with the land type.) We have listed 16 different possible buildings, and their “index” relative to the different land types. For example, building a farm on already developed land would not be the best choice.

K-means clustering is first conducted to remove the least favorable buildings (the ones with the least land area after convergence).

Initially, K-Means was done in Python, which was rather slow in speed. A single iteration took around one second. Unexpectedly, I was able to use my skills in game development, by using Unity. Although Unity is a game engine, it allows users to write computer shaders, which are essentially simplified GPU code, which is fast and efficient. Because K-Means is a process of iterating over each pixel, this can be easily done with GPU programming, where all pixels (unit of land) is processed simultaneously. 

This is a GPU function that does K-Means clustering. As seen, it calculates a “distance” which is in fact a combination of Euclidean distance and the overall “fitness” of that building. To further optimize it, by adding an additional z layer, one would be able to compute 100 different maps at the same time. Why would this be useful?

Because K-Means clustering introduces randomness, in the form of the initial seeds that are given (the initial position and type of the buildings), this means that a specific convergence might not be the best result. We were able to use the genetic algorithm to “evolve” the set of initial conditions. Genetic algorithm works by mimicking natural evolution, after every convergence, the set of genes, or initial conditions, that yield the highest results, will “reproduce”, while the ones with the least favorable results, will be eliminated. So every turn, we can have 100 different variations of the same conditions; After convergence, remove the 50 with the least scores, and use the most favorable 50 conditions to reproduce to 100 conditions again (Crossing the genes by mixing the conditions). Because we are able to compute 100 maps at the same time, this meant the genetic algorithm version of the clustering worked almost at the same pace as the prior one.

Unity also handles graphical output, which means it's easy to visualize our results. For example, this is a screenshot taken from Unity containing all the information we need to identify the details. The map contains the various building types with a legend on the bottom. (Purple = 0, Yellow = 1, and then we find the corresponding index to the building).

For instance, Evolution Iteration simply refers to the number of “evolutions” that have occurred, in this case, it is 770. Highest Index refers to the highest overall score (indicator of how well the land was utilized) that has been seen, which is also the solution we see in the map. Iterations since last change is the amount of iteration since the best solution was replaced (a better solution has occurred). 325 means that, for 325 revolutions, the current solution is still the most optimal. We can consider this to be converged. Which means that we found an optimal / “best” solution.

This was Problem A of IMMC 2023. It can be accessed here:

The other problem we did was Problem D. The paper can be accessed here:

We were invited to present our works at the Hong Kong University of Science and Technology (HKUST). 

Luckily, the judges didn't ask anything that was too difficult. They did point out a mistake in which we mistook kW for kWh. But it did go rather well.

We were given the Outstanding designation for our work in IMMC2023. I still remembered staying up for 4 hours to 6AM to work on the GPU code. Who knew you could use Unity for maths?