My Master’s Thesis Project gave me a taste for research problems in combinatorial optimization and through its completion I learned how to design a solver for the ground up. I also developed some novel enhancements unique to my solution approach.

My Master’s Thesis project at WPI was the construction of a novel method for solving a particular class of Integer Polynomial Program that supported exact solutions for a range of inequality right hand side constraints (a range of budgets), in contrast to prior approaches which focus on solving for only a fixed right hand side or only support Integer Linear Programs. I will take a step back shortly and explain what all of that means (or you can read the full thesis for a more in-depth look at things), but first I will explain the results. By employing the new method, enabled by the intelligent use of an R* tree data structure, that I called a “Minimal R* Tree”, I was able to solve for thousands of right hand sides on Quadratic Knapsack Problems generated by a standard construction in the time it would usually take to solve for ~30-40 conservatively. These problems are NP-hard and can take minutes or hours to solve exactly for even modest problem sizes.

This post will be added to when I get the time to update it with the details and ideally include additional improvements I have made post-thesis. Unfortunately it is a quite in depth topic (my thesis is over 60 pages, and somewhat information dense) so my initial go at describing it was short-lived.