Analysis of a class of nonlinear knapsack problems Conference Paper uri icon


  • 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.

published proceedings

  • 2006 IIE Annual Conference and Exhibition

author list (cited authors)

  • Sharkey, T. C., Romeijn, H. E., & Geunes, J.

complete list of authors

  • Sharkey, TC||Romeijn, HE||Geunes, J

publication date

  • December 2006