تعداد نشریات | 48 |
تعداد شمارهها | 1,653 |
تعداد مقالات | 17,968 |
تعداد مشاهده مقاله | 5,414,715 |
تعداد دریافت فایل اصل مقاله | 2,497,645 |
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 | ||
آمار تعداد مشاهده مقاله: 16 |