Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Metaheuristic and heuristic applications to the concave knapsack problem
Thesis (MCom)--Stellenbosch University, 2023.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2023
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613958316228608 |
|---|---|
| access_status_str | Open Access |
| author | Heinrich, Bowen |
| author2 | Visagie, Stephan |
| author_browse | Heinrich, Bowen Visagie, Stephan |
| author_facet | Visagie, Stephan Heinrich, Bowen |
| author_sort | Heinrich, Bowen |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (MCom)--Stellenbosch University, 2023. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/127192 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:44:24.894Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2023 |
| publishDateRange | 2023 |
| publishDateSort | 2023 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/127192 Metaheuristic and heuristic applications to the concave knapsack problem Heinrich, Bowen Visagie, Stephan Stellenbosch University. Faculty of Economic and Management Sciences. Dept. of Logistics. Computer algorithms Heuristic programming Problem solving -- Data processing Heuristic algorithms UCTD Thesis (MCom)--Stellenbosch University, 2023. ENGLISH SUMMARY: Non-linear knapsack problems are among the simplest non-linear constrained optimisation problems consisting of an objective function to be minimised subject to a single constraint, along with bounds on the variables. The non-convex case is significantly more difficult to solve than the convex case, and as such, it has not been studied as much as the convex case. In particular, no literature exists on using metaheuristics to solve the problem. Four algorithms were developed exploiting the KKT necessary conditions to solve the concave knapsack problem. A result from KKT theory is that an optimal solution to the concave knapsack problem has at most one variable with a value strictly between its bounds. A variable neighbourhood search (VNS) and a tabu search algorithm (TS-I) were developed using a neighbourhood structure in which a move is performed by flipping variables from one bound to another. A second tabu search algorithm (TS-II) was developed in which a move is performed by setting a variable that is strictly between its bounds to either its lower or upper bound. The fourth algorithm developed (DPH) exploits two trends that were observed in the optimal solutions of test instances to reduce the solution space of the problem. Dynamic programming is then used to solve this reduced problem in a reasonable amount of time. A total of 2 187 diverse test instances were generated in order to evaluate the performance of the developed algorithms on several metrics. If the goal is simply to minimise the objective function value as quickly as possible, VNS is recommended if the number of variables and the minimum average slope of the functions is small. If instead the minimum average slope is large and the upper bounds are too, TS-I is recommended while DPH is recommended if the upper bounds are small. If the number of variables is large or the minimum upper bound of the variables is small, DPH is recommended and TS-I is recommended for an intermediate number of variables. If the goal is to solve to optimality as often as possible, DPH is recommended unless the minimum average slope of the functions is small or the upper bounds are large. In that case, TS-I is recommended. The recommendation regarding the solution time depends on what level of solution quality is considered acceptable. The TS-II outperformed the other algorithms for all but one of the test instances in terms of solution time. The speed of this algorithm, however, comes at the cost of solution quality as this algorithm also obtained the worst solutions. The algorithm VNS was the next fastest, but also did not perform as well as the remaining two algorithms. The TS-I and DPH obtained solutions of similar quality with comparable solution time overall. For small upper bounds, small right-hand side of the constraint and large minimum average slope of the functions, DPH outperformed TS-I in terms of solution time. The DPH obtained the optimal solution in the most instances overall, but when the minimum average slope of the functions was small or the upper bounds were large, it was outperformed by TS-I. AFRIKAANSE OPSOMMING: Nie-lineere knapsakprobleme is van die eenvoudigste nie-lineere beperkte optimeringsprobleme, wat bestaan uit ’n doelfunksie wat geminimeer moet word onderhewig aan ’n enkele beperking, tesame met grense op die veranderlikes. Die nie-konvekse geval is aansienlik moeiliker as die konvekse geval om op te los, en as sodanig is dit nie soveel bestudeer as die konvekse geval nie. Daar bestaan veral geen literatuur oor die gebruik van metaheuristieke om die probleem op te los nie. Vier algoritmes is ontwikkel wat die KKT nodige voorwaardes ontgin om die konkawe knapsakprobleem op te los. ’n Gevolg uit KKT-teorie is dat ’n optimale oplossing vir die konkawe knapsakprobleem hoogtens een veranderlike het met ’n waarde streng tussen sy grense. ’n Veranderbare-omgewing-soektog (VNS) en ’n taboe-soektog (TS-I) is ontwikkel wat ’n omgewing gebruik waarin ’n skuif bestaan uit veranderlikes van een grens na die ander te verander. ’n Tweede taboe-soektog (TS-II) is ontwikkel waarin ’n skuif uitgevoer word deur die veranderlike met ’n waarde streng tussen sy grense te stel na ´of sy ondergrens ´of sy bogrens. Die vierde algoritme (DPH) ontgin twee tendense wat waargeneem is in die optimale oplossings van toetsprobleme om die oplossingsruimte van die probleem te verminder. Dinamiese programmering word dan gebruik om hierdie verkleinde probleem binne ’n redelike tyd op te los. ’n Totaal van 2 187 toetsgevalle is gegenereer om die prestasie van die ontwikkelde algoritmes te evalueer. As die doel eenvoudig is om die doelfunksiewaarde vinnig minimeer, word VNS aanbeveel as die aantal veranderlikes en die minimum gemiddelde helling van die funksies klein is. As die minimum gemiddelde helling groot is en die bogrense ook groot is, word TS-I aanbeveel terwyl DPH aanbeveel word as die bogrense klein is. As die aantal veranderlikes groot is of die minimum bogrens klein is, word DPH aanbeveel en TS-I word aanbeveel vir ’n intermediere getal veranderlikes. As die doel is om so dikwels as moontlik tot optimaliteit op te los, word DPH aanbeveel tensy die minimum gemiddelde helling van die funksies klein is of die bogrense groot is. In daardie geval, word TS-I aanbeveel. Die aanbeveling betreffende die oplossingstyd hang af van watter vlak van oplossingskwaliteit as aanvaarbaar beskou word. Die TS-II het beter gevaar as die ander algoritmes vir al die toetsgevalle behalwe een in terme van oplossings tyd. Die spoed van hierdie algoritme kom egter ten koste van oplossingskwaliteit aangesien hierdie algoritme ook die swakste oplossings verkry het. Die VNS was die volgende vinnigste, maar het ook nie so goed presteer soos die oorblywende twee algoritmes nie. Die TS-I en DPH het oplossings van soortgelyke gehalte met vergelykbare oplossingstyd oor die algemeen verkry. Vir klein bogrense, klein regterkant van die beperking end groot minimum gemiddelde helling van die funksies, het DPH beter gevaar as TS-I in terme van oplossingstyd. Die DPH het die optimale oplossing in die meeste gevalle oor die algemeen verkry, maar wanneer die gemiddelde helling van die funksies klein was of die bogrense groot was, het TS-I beter presteer. Masters 2023-02-22T10:54:14Z 2023-05-18T07:09:02Z 2023-02-22T10:54:14Z 2023-05-18T07:09:02Z 2023-03 Thesis http://hdl.handle.net/10019.1/127192 en_ZA Stellenbosch University viii, 60 pages : illustrations application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Computer algorithms Heuristic programming Problem solving -- Data processing Heuristic algorithms UCTD Heinrich, Bowen Metaheuristic and heuristic applications to the concave knapsack problem |
| title | Metaheuristic and heuristic applications to the concave knapsack problem |
| title_full | Metaheuristic and heuristic applications to the concave knapsack problem |
| title_fullStr | Metaheuristic and heuristic applications to the concave knapsack problem |
| title_full_unstemmed | Metaheuristic and heuristic applications to the concave knapsack problem |
| title_short | Metaheuristic and heuristic applications to the concave knapsack problem |
| title_sort | metaheuristic and heuristic applications to the concave knapsack problem |
| topic | Computer algorithms Heuristic programming Problem solving -- Data processing Heuristic algorithms UCTD |
| url | http://hdl.handle.net/10019.1/127192 |
| work_keys_str_mv | AT heinrichbowen metaheuristicandheuristicapplicationstotheconcaveknapsackproblem |