A class of nonlinear nonseparable continuous knapsack and multiple-choice knapsack problems

• 成果类型: Article
• 署名作者: Sharkey, Thomas C.; Romeijn, H. Edwin; Geunes, Joseph
• 署名单位: Rensselaer Polytechnic Institute; University of Michigan System; University of Michigan; State University System of Florida; University of Florida
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-009-0274-9
• 发表日期: 2011
• 页码: 69-96
• 关键词: o(n) algorithm; efficient algorithm; optimization; uncertainty; selection

摘要

This paper considers a general class of continuous, nonlinear, and nonseparable knapsack problems, special cases of which arise in numerous operations and financial contexts. We develop important properties of optimal solutions for this problem class, based on the properties of a closely related class of linear programs. Using these properties, we provide a solution method that runs in polynomial time in the number of decision variables, while also depending on the time required to solve a particular one-dimensional optimization problem. Thus, for the many applications in which this one-dimensional function is reasonably well behaved (e.g., unimodal), the resulting algorithm runs in polynomial time. We next develop a related solution approach to a class of continuous, nonlinear, and nonseparable multiple-choice knapsack problems. This algorithm runs in polynomial time in both the number of variables and the number of variants per item, while again dependent on the complexity of the same one-dimensional optimization problem as for the knapsack problem. Computational testing demonstrates the power of the proposed algorithms over a commercial global optimization software package.