A Class of Continuous Separable Nonlinear Multidimensional Knapsack Problems

• 作者: Bin Zhang Yu Wang Zhe Lin
• 来源期刊: 美国运筹学期刊(英文)
• 学科: 数学
• 关键词: NONLINEAR PROGRAMMING Convex PROGRAMMING MULTIDIMENSIONAL KNAPSACK SEPARABLE KNAPSACK LAGRANGIAN Relaxation
• 年，卷（期）: 2018,（4）
• 页码范围: 266-280
• 页数: 15页
• 分类号: O1

摘要

The nonlinear multidimensional knapsack problem is defined as the minimization of a convex function with multiple linear constraints. The methods developed for nonlinear multidimensional programming problems are often applied to solve the nonlinear multidimensional knapsack problems, but they are inefficient or limited since most of them do not exploit the characteristics of the knapsack problems. In this paper, by establishing structural properties of the continuous separable nonlinear multidimensional knapsack problem, we develop a multi-tier binary solution method for solving the continuous nonlinear multidimensional knapsack problems with general structure. The computational complexity is polynomial in the number of variables. We presented two examples to illustrate the general application of our method and we used statistical results to show the effectiveness of our method.