On the effcient solvability of a simple class of nonlinear knapsack problems

Abstract

In this paper the effcient solvability of a class of nonlinear knapsack problems are investigated by means of the problem\'s necessary and suffcient conditions. It is shown that, from the general theory, it is impossible to determine suffcient conditions for a solution to be globally optimal. Furthermore, it is shown that even for the smallest possible instance of this problem it is, in general, possible to have an arbitrary large number of solutions for which the necessary conditions hold. These results are then generalised to larger instances of the problem. A possible solution approach is applied to sets of randomly generated problems that utilises the necessary conditions together with the branch-and-bound technique in an attempt to limit the search space. This approach solves mixed 0/1 knapsack problems in order to end all possible solutions satisfying the necessary conditions. Due to the large number of solutions satisfying the necessary conditions the proposed solution approach takes substantially longer than existing branch-and-bound algorithms together with linear enveloping when applied to the same set of problems. This result renders the proposed approach not very effcient.

Keywords: Nonlinear knapsack problem, nonconvex optimisation, resource allocation problem.

ORiON Vol. 24 (1) 2008: pp. 1-15