论文标题
一种解决连续排名的两阶段方法
A Two-Phase Method for Solving Continuous Rank-One Quadratic Knapsack Problems
论文作者
论文摘要
在本文中，我们提出了一种两相算法，用于解决连续的排名二次背包问题（R1QKP）。特别是，我们在没有背包约束的情况下研究问题的解决方案结构。在这种情况下，我们建议使用$ O（n \ log n）$算法。然后，我们使用解决方案结构提出一个$ O（n^2 \ log n）$算法，该算法找到一个包含R1QKP Lagrangian Dual的最佳值的间隔。在第二阶段，我们使用传统的单变化优化方法解决了受限制的拉格朗日双重问题。我们对随机实例进行计算测试，并将算法与通用求解器CPLEX进行比较。
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(n\log n)$ algorithm 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 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.
