TITLE:
A Class of Continuous Separable Nonlinear Multidimensional Knapsack Problems
AUTHORS:
Bin Zhang, Zhe Lin, Yu Wang
KEYWORDS:
Nonlinear Programming, Convex Programming, Multidimensional Knapsack, Separable Knapsack, Lagrangian Relaxation
JOURNAL NAME:
American Journal of Operations Research,
Vol.8 No.4,
July
2,
2018
ABSTRACT: 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.