Open Access. Powered by Scholars. Published by Universities.®
![Digital Commons Network](http://assets.bepress.com/20200205/img/dcn/DCsunburst.png)
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
The Precedence-Constrained Quadratic Knapsack Problem, Changkun Guan
The Precedence-Constrained Quadratic Knapsack Problem, Changkun Guan
Honors Theses
This thesis investigates the previously unstudied Precedence-Constrained Quadratic Knapsack Problem (PC-QKP), an NP-hard nonlinear combinatorial optimization problem. The PC-QKP is a variation of the traditional Knapsack Problem (KP) that introduces several additional complexities. By developing custom exact and approximate solution methods, and testing these on a wide range of carefully structured PC-QKP problem instances, we seek to identify and understand patterns that make some cases easier or harder to solve than others. The findings aim to help develop better strategies for solving this and similar problems in the future.