Breakpoint searching algorithms for the continuous quadratic knapsack problem

• 成果类型: Article
• 署名作者: Kiwiel, Krzysztof C.
• 署名单位: Polish Academy of Sciences; Systems Research Institute of the Polish Academy of Sciences
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-006-0050-z
• 发表日期: 2008
• 页码: 473-491
• 关键词: resource-allocation; time algorithms; o(n) algorithm; projection; simplex; vector

摘要

We give several linear time algorithms for the continuous quadratic knapsack problem. In addition, we report cycling and wrong-convergence examples in a number of existing algorithms, and give encouraging computational results for large-scale problems.