A two-phase method for solving continuous rank-one quadratic knapsack problems

We propose a two-phase algorithm for solving continuous rank-one quadratic knapsack problems (R۱QKPs). In particular, we study the solution structure of the problem without the knapsack constraint. In fact, an O(n\log n) algorithm is suggested in this case. We then use the solution structure to propose an O(n^۲\log n) algorithm that finds an interval containing the optimal value of the Lagrangian dual of R۱QKP. In the second phase, we solve the Lagrangian dual problem using a traditional single-variable optimization method. We perform a computational test on random instances and compare our algorithm with the general solver CPLEX.

Keywords:

Quadratic Knapsack Problem , Line-Sweep Algorithm , Large-Scale Optimization