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

Iranian Journal of Numerical Analysis and Optimization

مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 23 تیر 1401  

نوع مقاله: SPECIAL ISSUE- Volume 12 No 2 (Summer 2022)

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

نویسنده

Ehsan Monabbati

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

چکیده

In this paper, we propose a two-phase algorithm for solving continuous rank-one quadratic knapsack problems (R1QKP).
 In particular, we study the solution structure of the problem without the knapsack constraint. We propose an $O(nlog n)$ algorithm in this case. We then use the solution structure to propose an $O(n^2log n) $ algorithm that finds an interval containing the optimal value of the Lagrangian dual of R1QKP. In the second phase, we solve the restricted 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؛ Large-scale optimization