Thomas C. Sharkey, H. Edwin Romeijn, Joseph Geunes
A class of nonlinear monseparable continuous
knapsack and multiple-choice knapsack problems.
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.