Precedence-Constrained Quadratic Knapsack Problem
My honors thesis introduced and studied the Precedence-Constrained Quadratic Knapsack Problem (PC-QKP), a previously unstudied NP-hard nonlinear combinatorial optimization problem that combines the quadratic knapsack objective with precedence constraints on item selection.
Key contributions:
- Developed an exact solution method for the PC-QKP
- Designed and experimented with heuristics and metaheuristics
- Generated difficult problem instances to probe what makes the problem hard, informing solution strategies for this and similar problems
Thesis advisor: Dr. Lucas Waddell