On the efficient solvability of a simple class of nonlinear knapsack problems
| dc.contributor.author | Visagie, Stephan E. | en_ZA |
| dc.date.accessioned | 2012-08-02T16:38:51Z | |
| dc.date.available | 2012-08-02T16:38:51Z | |
| dc.date.issued | 2008 | |
| dc.description | 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. | |
| dc.description | The original publication is available at http://orion.journals.ac.za/pub | |
| dc.description.abstract | 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. | en_ZA |
| dc.description.uri | http://orion.journals.ac.za/pub/article/view/56 | |
| dc.description.version | Publisher's version | en_ZA |
| dc.format.extent | 16 pages | |
| dc.identifier.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 | en_ZA |
| dc.identifier.issn | 2224-0004 (online) | |
| dc.identifier.issn | 0259-191X (print) | |
| dc.identifier.other | doi:10.5784/24-1-56 | |
| dc.identifier.uri | http://hdl.handle.net/10019.1/21965 | |
| dc.language.iso | en_ZA | en_ZA |
| dc.publisher | Operations Research Society of South Africa | |
| dc.rights.holder | Author retains copyright | |
| dc.subject | Nonlinear knapsack problem | en_ZA |
| dc.subject | Resource allocation problem | en_ZA |
| dc.subject | Nonconvex optimisation | en_ZA |
| dc.title | On the efficient solvability of a simple class of nonlinear knapsack problems | en_ZA |
| dc.type | Article | en_ZA |