Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Algoritmes vir die maksimering van konvekse en verwante knapsakprobleme
Thesis (PhD (Logistics))--University of Stellenbosch, 2007.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | Afrikaans |
| Published: |
Stellenbosch : University of Stellenbosch
2008
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613938787549184 |
|---|---|
| access_status_str | Open Access |
| author | Visagie, Stephan E. |
| author2 | De Kock, H. C. |
| author_browse | De Kock, H. C. Visagie, Stephan E. |
| author_facet | De Kock, H. C. Visagie, Stephan E. |
| author_sort | Visagie, Stephan E. |
| collection | Thesis |
| dc_rights_str_mv | University of Stellenbosch |
| description | Thesis (PhD (Logistics))--University of Stellenbosch, 2007. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/1082 |
| institution | Stellenbosch University (South Africa) |
| language | Afrikaans |
| last_indexed | 2026-06-10T12:44:05.289Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2008 |
| publishDateRange | 2008 |
| publishDateSort | 2008 |
| publisher | Stellenbosch : University of Stellenbosch |
| publisherStr | Stellenbosch : University of Stellenbosch |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/1082 Algoritmes vir die maksimering van konvekse en verwante knapsakprobleme Visagie, Stephan E. De Kock, H. C. University of Stellenbosch. Faculty of Economic and Management Sciences. Dept. of Logistics. Algoritme Knapsack problem (Mathematics) Computer algorithms Mathematical optimization Convex programming Dissertations -- Logistics Theses -- Logistics Thesis (PhD (Logistics))--University of Stellenbosch, 2007. In this dissertation original algorithms are introduced to solve separable resource allocation problems (RAPs) with increasing nonlinear functions in the objective function, and lower and upper bounds on each variable. Algorithms are introduced in three special cases. The first case arises when the objective function of the RAP consists of the sum of convex functions and all the variables for these functions range over the same interval. In the second case RAPs with the sum of convex functions in the objective function are considered, but the variables of these functions can range over different intervals. In the last special case RAPs with an objective function comprising the sum of convex and concave functions are considered. In this case the intervals of the variables can range over different values. In the first case two new algorithms, namely the fraction and the slope algorithm are presented to solve the RAPs adhering to the conditions of the case. Both these algorithms yield far better solution times than the existing branch and bound algorithm. A new heuristic and three new algorithms are presented to solve RAPs falling into the second case. The iso-bound heuristic yields, on average, good solutions relative to the optimal objective function value in faster times than exact algorithms. The three algorithms, namely the iso-bound algorithm, the branch and cut algorithm and the iso-bound branch and cut algorithm also yield considerably beter solution times than the existing branch and bound algorithm. It is shown that, on average, the iso-bound branch and cut algorithm yields the fastest solution times, followed by the iso-bound algorithm and then by die branch and cut algorithm. In the third case the necessary and sufficient conditions for optimality are considered. From this, the conclusion is drawn that search techniques for points complying with the necessary conditions will take too long relative to branch and bound techniques. Thus three new algorithms, namely the KL, SKL and IKL algorithms are introduced to solve RAPs falling into this case. These algorithms are generalisations of the branch and bound, branch and cut, and iso-bound algorithms respectively. The KL algorithm was then used as a benchmark. Only the IKL algorithm yields a considerable improvement on the KL algorithm. Doctoral 2008-08-06T12:42:30Z 2010-06-01T08:12:05Z 2008-08-06T12:42:30Z 2010-06-01T08:12:05Z 2007-03 Thesis http://hdl.handle.net/10019.1/1082 af University of Stellenbosch application/pdf Stellenbosch : University of Stellenbosch |
| spellingShingle | Algoritme Knapsack problem (Mathematics) Computer algorithms Mathematical optimization Convex programming Dissertations -- Logistics Theses -- Logistics Visagie, Stephan E. Algoritmes vir die maksimering van konvekse en verwante knapsakprobleme |
| title | Algoritmes vir die maksimering van konvekse en verwante knapsakprobleme |
| title_full | Algoritmes vir die maksimering van konvekse en verwante knapsakprobleme |
| title_fullStr | Algoritmes vir die maksimering van konvekse en verwante knapsakprobleme |
| title_full_unstemmed | Algoritmes vir die maksimering van konvekse en verwante knapsakprobleme |
| title_short | Algoritmes vir die maksimering van konvekse en verwante knapsakprobleme |
| title_sort | algoritmes vir die maksimering van konvekse en verwante knapsakprobleme |
| topic | Algoritme Knapsack problem (Mathematics) Computer algorithms Mathematical optimization Convex programming Dissertations -- Logistics Theses -- Logistics |
| url | http://hdl.handle.net/10019.1/1082 |
| work_keys_str_mv | AT visagiestephane algoritmesvirdiemaksimeringvankonvekseenverwanteknapsakprobleme |