A two-phase method for solvingcontinuous rank-one quadratic knapsackproblems

We propose a two-phase algorithm for solving continuous rank-onequadratic knapsack problems (r1qkps). in particular, we study the solutionstructure of the problem without the knapsack constraint. in factan o(n log n) algorithm is suggested in this case. we then use the solutionstructure to propose an o(n^2 log n) algorithm that finds an intervalcontaining the optimal value of the lagrangian dual of r1qkp. in thesecond phase, we solve the lagrangian dual problem using a traditionalsingle-variable optimization method. we perform a computational teston random instances and compare our algorithm with the general solvercplex.