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

Visagie, Stephan E. (2008)

CITATION: Visagie, S. E. 2008. On the efficient solvability of a simple class of nonlinear knapsack problems. ORiON, 24(1):1-15, doi:10.5784/24-1-56.

The original publication is available at http://orion.journals.ac.za/pub


ENGLISH SUMMARY : In this paper the e cient solvability of a class of nonlinear knapsack problems are investigated by means of the problem's necessary and su cient conditions. It is shown that, from the general theory, it is impossible to determine su cient 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 nd 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 e cient.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/21965
This item appears in the following collections: