Analysis of a class of nonlinear knapsack problems
Conference Paper
Overview
Overview
abstract
We study a nonlinear knapsack problem whose objective function consists of the difference between a linear function of the variables and a general nonlinear function of another linear function of the variables. The special structure of this problem allows us to provide a bound on the number of fractional variables in an optimal solution and analysis of the KKT conditions leads to an effective solution method. We develop a condition under which our method is efficient and show that if this condition is violated, determining the optimal solution with the fewest number of fractional variables is NP-hard.
