Generalisations of non-linear knapsack problems

Abstract

This paper presents an efficient algorithm for solving the Lagrangean dual of non-linear knapsack problems with additional nested constraints. The dual solution provides a feasible primal solution (if it exists) and associated lower and upper bounds on the optimal objective function value of the primal problem. Computational experience is cited indicating computation time, number of dual iterations, and tightness of the bounds.