I spent the summer after my sophomore year participating in a student-faculty research project with my advisor Dr. Richard Forrester at Dickinson College. The project was a Computational Study of Solution Techniques for 0-1 Quadratic Programs. I came into the project having just taken a course in Operations Research with Forrester which sparked my interest in the topic. In that course we covered creating linear programs that model a wide range of real world optimization problems, and how they can be solved efficiently using the Simplex method. Linear programming is the process of maximizing a linear objective function subject to a series of linear constraints.

A quadratic program is just like a linear program except that the objective function, the function you are trying to minimize or maximize, is quadratic rather than linear. These, it turns out, are much more difficult to solve efficiently. A wide variety of solution techniques exist and have been proposed as optimal for very particular cases but there is no clear agreement on which methods work best in general. The goal of our research was thus to investigate, via a computational study, which techniques perform best on which problem types.

In order to accomplish this task, we first had to generate a testbed. We wrote code to randomly generate instances of a number of different common problem types such as quadratic knapsack and the quadratic semi-assignment problem. Next, we had to implement many different solution techniques to run on the testbed. Many of these techniques involved linearization, the process of converting a quadratic program into an equivalent linear program (at the cost of many added constraints).

You can find my entire codebase from the project here.