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

Iranian Journal of Numerical Analysis and Optimization

مقاله 5، دوره 12، Issue 3 (Special Issue) - شماره پیاپی 23، بهمن 2022، صفحه 567-584   

نوع مقاله: Research Article

شناسه دیجیتال (DOI): 10.22067/ijnao.2022.70644.1096

نویسنده

S.E. Monabbati^*

Department of Mathematics, Faculty of Mathematical Sciences, Alzahra University, Tehran, Iran.

چکیده

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.

کلیدواژه‌ها

Quadratic Knapsack Problem؛ Line-Sweep Algorithm

مراجع