{"id":{"repo_id":"vu-aus","oai_identifier":"oai:eprints.vu.edu.au:17924"},"canonical_url":"https://search.dev.ndltd.org/etd/vu-aus/oai:eprints.vu.edu.au:17924","repository":{"repo_id":"vu-aus","name":"Victoria University (Australia)","base_url":"https://vuir.vu.edu.au/cgi/oai2"},"display":{"title":"A complementary heuristic for the unbounded knapsack problem","abstract":"As a solution algorithm for Unbounded Knapsack Problem, the performance analysis of density-ordered greedy heuristic, weight-ordered greedy heuristic, value-ordered greedy heuristic, extended greedy heuristic and total-value heuristic has been done. Empirical experiments on different test problems have been analysed and reported. Problem instances with a very large number of undominated items were generated in addition to the types of instances suggested by Martello and Toth (1990). Theoretically, the lower bound on the performance for total-value heuristic is better than the corresponding lower bounds for the densityordered greedy heuristic and the extended greedy heuristic as discussed by White (1992) and Kohli and Krishnamurti (1992). The computational tests fail to show clear superiority of any particular heuristic algorithm, although each heuristic produces good quality solutions. If the combination of the density-ordered greedy and the total-value greedy heuristics are considered then the combination shows complementary effect. A new heuristic algorithm incorporating the structural properties of the density-ordered greedy heuristic and the total-value greedy heuristic is developed and its complementary effect studied. It was found that the combination of the density-ordered greedy heuristic, the extended greedy heuristic, the total-value greedy heuristic and the new complementary heuristic gives a better performance result than the single best heuristic in the combination.","abstract_html":"As a solution algorithm for Unbounded Knapsack Problem, the performance analysis of density-ordered greedy heuristic, weight-ordered greedy heuristic, value-ordered greedy heuristic, extended greedy heuristic and total-value heuristic has been done. Empirical experiments on different test problems have been analysed and reported. Problem instances with a very large number of undominated items were generated in addition to the types of instances suggested by Martello and Toth (1990). Theoretically, the lower bound on the performance for total-value heuristic is better than the corresponding lower bounds for the densityordered greedy heuristic and the extended greedy heuristic as discussed by White (1992) and Kohli and Krishnamurti (1992). The computational tests fail to show clear superiority of any particular heuristic algorithm, although each heuristic produces good quality solutions. If the combination of the density-ordered greedy and the total-value greedy heuristics are considered then the combination shows complementary effect. A new heuristic algorithm incorporating the structural properties of the density-ordered greedy heuristic and the total-value greedy heuristic is developed and its complementary effect studied. It was found that the combination of the density-ordered greedy heuristic, the extended greedy heuristic, the total-value greedy heuristic and the new complementary heuristic gives a better performance result than the single best heuristic in the combination.","abstract_has_math":false,"creators":["Iyer, Swarna Chitra"],"institution":"Victoria University of Technology","degree_name":"other","degree_level":"rmaster","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":1997,"date_issued":"1997","date_published":"1997","updated_at":"2026-07-24T06:33:22Z","subjects":["0102 Applied Mathematics","0103 Numerical and Computational Mathematics","School of Engineering and Science"],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Iyer, Swarna Chitra"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["1997"]},{"key":"dc:date.issued","label":"Date","values":["1997"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["Department of Computer and Mathematical Sciences"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["Victoria University of Technology"]},{"key":"dc:relation.isreferencedby","label":"Dc Relation Isreferencedby","values":["https://vuir.vu.edu.au/17924/"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["rmaster"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["other"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["0102 Applied Mathematics","0103 Numerical and Computational Mathematics","School of Engineering and Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://vuir.vu.edu.au/17924/1/IYER_1997compressed.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["As a solution algorithm for Unbounded Knapsack Problem, the performance analysis of density-ordered greedy heuristic, weight-ordered greedy heuristic, value-ordered greedy heuristic, extended greedy heuristic and total-value heuristic has been done. Empirical experiments on different test problems have been analysed and reported. Problem instances with a very large number of undominated items were generated in addition to the types of instances suggested by Martello and Toth (1990). Theoretically, the lower bound on the performance for total-value heuristic is better than the corresponding lower bounds for the densityordered greedy heuristic and the extended greedy heuristic as discussed by White (1992) and Kohli and Krishnamurti (1992). The computational tests fail to show clear superiority of any particular heuristic algorithm, although each heuristic produces good quality solutions. If the combination of the density-ordered greedy and the total-value greedy heuristics are considered then the combination shows complementary effect. A new heuristic algorithm incorporating the structural properties of the density-ordered greedy heuristic and the total-value greedy heuristic is developed and its complementary effect studied. It was found that the combination of the density-ordered greedy heuristic, the extended greedy heuristic, the total-value greedy heuristic and the new complementary heuristic gives a better performance result than the single best heuristic in the combination."]},{"key":"dc:format","label":"Dc Format","values":["text"]},{"key":"dc:title","label":"Title","values":["A complementary heuristic for the unbounded knapsack problem"]}]}],"canonical_facts":{"dc:creator":["Iyer, Swarna Chitra"],"dc:date":["1997"],"dc:date.issued":["1997"],"dc:description.abstract":["As a solution algorithm for Unbounded Knapsack Problem, the performance analysis of density-ordered greedy heuristic, weight-ordered greedy heuristic, value-ordered greedy heuristic, extended greedy heuristic and total-value heuristic has been done. Empirical experiments on different test problems have been analysed and reported. Problem instances with a very large number of undominated items were generated in addition to the types of instances suggested by Martello and Toth (1990). Theoretically, the lower bound on the performance for total-value heuristic is better than the corresponding lower bounds for the densityordered greedy heuristic and the extended greedy heuristic as discussed by White (1992) and Kohli and Krishnamurti (1992). The computational tests fail to show clear superiority of any particular heuristic algorithm, although each heuristic produces good quality solutions. If the combination of the density-ordered greedy and the total-value greedy heuristics are considered then the combination shows complementary effect. A new heuristic algorithm incorporating the structural properties of the density-ordered greedy heuristic and the total-value greedy heuristic is developed and its complementary effect studied. It was found that the combination of the density-ordered greedy heuristic, the extended greedy heuristic, the total-value greedy heuristic and the new complementary heuristic gives a better performance result than the single best heuristic in the combination."],"dc:format":["text"],"dc:identifier.uri":["https://vuir.vu.edu.au/17924/1/IYER_1997compressed.pdf"],"dc:language":["en"],"dc:publisher.department":["Department of Computer and Mathematical Sciences"],"dc:publisher.institution":["Victoria University of Technology"],"dc:relation.isreferencedby":["https://vuir.vu.edu.au/17924/"],"dc:subject":["0102 Applied Mathematics","0103 Numerical and Computational Mathematics","School of Engineering and Science"],"dc:title":["A complementary heuristic for the unbounded knapsack problem"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["rmaster"],"dc:type.qualificationname":["other"]},"updated_at":"2026-07-24T06:33:22Z"}