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

Abstract

We propose a two-phase algorithm for solving continuous rank-one quadratic knapsack problems (R1QKPs). 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^2\log n)$ algorithm that finds an interval containing the optimal value of the Lagrangian dual of R1QKP. 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