Visualization of Multidimensional Multi-choice Knapsack Problem
Written in a compute shader using HLSL. Orchestrated with C#. Using Unity for ease of visualization.
Problem statement:
"There are four 1024x1024 pixel textures. In each texture, each pixel has a random RGB color. Pick exactly one pixel from each texture such that the total Red value of all chosen pixels is maximized, the total Green value of all chosen pixels is above some threshold, and the total Blue value of all chosen pixels is below a separate threshold."
In this visualization, each of the 4 textures are one quadrant of the resulting image. Better candidate pixels are pushed towards the center of the canvas, while worse candidates are pushed to the outside corners. This is a heuristic approach. It is not guaranteed to find the best solution in X steps. It has not been benchmarked. At each step of the simulation, quartets of pixels are evaluated according to a heuristic and given a score. The textures are then even-odd sorted according to these scores. There is a temperature component passed to the compute shader each frame. When the combination of temperature and a pixel's score is above a threshold, the simulation is allowed to sort pixels incorrectly on purpose. This is a type of simulated annealing that helps remove local maxima.
This simulation runs lightning fast thanks to the GPU's native multithreading capabilities.