{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T21:16:45Z","timestamp":1776374205408,"version":"3.51.2"},"reference-count":47,"publisher":"Emerald","issue":"9\/10","license":[{"start":{"date-parts":[[2014,11,3]],"date-time":"2014-11-03T00:00:00Z","timestamp":1414972800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.emerald.com\/insight\/site-policies"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014,11,3]]},"abstract":"<jats:sec><jats:title content-type=\"abstract-heading\">Purpose<\/jats:title><jats:p>\u2013 Hyper-heuristics are a class of high-level search techniques which operate on a search space of heuristics rather than directly on a search space of solutions. The purpose of this paper is to investigate the suitability of using genetic programming as a hyper-heuristic methodology to generate constructive heuristics to solve the multidimensional 0-1 knapsack problem<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Design\/methodology\/approach<\/jats:title><jats:p>\u2013 Early hyper-heuristics focused on selecting and applying a low-level heuristic at each stage of a search. Recent trends in hyper-heuristic research have led to a number of approaches being developed to automatically generate new heuristics from a set of heuristic components. A population of heuristics to rank knapsack items are trained on a subset of test problems and then applied to unseen instances.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Findings<\/jats:title><jats:p>\u2013 The results over a set of standard benchmarks show that genetic programming can be used to generate constructive heuristics which yield human-competitive results.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Originality\/value<\/jats:title><jats:p>\u2013 In this work the authors show that genetic programming is suitable as a method to generate reusable constructive heuristics for the multidimensional 0-1 knapsack problem. This is classified as a hyper-heuristic approach as it operates on a search space of heuristics rather than a search space of solutions. To our knowledge, this is the first time in the literature a GP hyper-heuristic has been used to solve the multidimensional 0-1 knapsack problem. The results suggest that using GP to evolve ranking mechanisms merits further future research effort.<\/jats:p><\/jats:sec>","DOI":"10.1108\/k-09-2013-0201","type":"journal-article","created":{"date-parts":[[2014,11,5]],"date-time":"2014-11-05T08:02:57Z","timestamp":1415174577000},"page":"1500-1511","source":"Crossref","is-referenced-by-count":40,"title":["A genetic programming hyper-heuristic for the multidimensional knapsack problem"],"prefix":"10.1108","volume":"43","author":[{"given":"John H","family":"Drake","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew","family":"Hyde","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Khaled","family":"Ibrahim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ender","family":"Ozcan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"140","reference":[{"key":"key2020122723141956000_b1","doi-asserted-by":"crossref","unstructured":"Ak\u00e7ay, Y. , Li, H. and Xu, S.H. (2007), \u201cGreedy algorithm for the general multidimensional knapsack problem\u201d, Annals of Operations Research , Vol. 150 No. 1, pp. 17-29.","DOI":"10.1007\/s10479-006-0150-4"},{"key":"key2020122723141956000_b2","doi-asserted-by":"crossref","unstructured":"Allen, S. , Burke, E.K. , Hyde, M. and Kendall, G. (2009), \u201cEvolving reusable 3d packing heuristics with genetic programming\u201d, Proceedings of GECCO 2009, Montreal, pp. 931-938.","DOI":"10.1145\/1569901.1570029"},{"key":"key2020122723141956000_b3","doi-asserted-by":"crossref","unstructured":"Bader-El-Den, M. and Poli, R. (2008), \u201cGenerating sat local-search heuristics using a gp hyper-heuristic framework\u201d, Artificial Evolution, Vol. 4926 of LNCS, Springer, Berlin\/Heidelberg, pp. 37-49.","DOI":"10.1007\/978-3-540-79305-2_4"},{"key":"key2020122723141956000_b4","doi-asserted-by":"crossref","unstructured":"Boussier, S. , Vasquez, M. , Vimont, Y. , Hanafi, S. and Michelon, P. (2010), \u201cA multi-level search strategy for the 0-1 multidimensional knapsack problem\u201d, Discrete Applied Mathematics , Vol. 158 No. 2, pp. 97-109.","DOI":"10.1016\/j.dam.2009.08.007"},{"key":"key2020122723141956000_b5","doi-asserted-by":"crossref","unstructured":"Burke, E.K. , Gendreau, M. , Hyde, M. , Kendall, G. , Ochoa, G. , \u00d6zcan, E. and Qu, R. (2013), \u201cHyper-heuristics: A survey of the state of the art\u201d, To Appear in the Journal of the Operational Research Society , Vol. 64 No. 12, pp. 1695-1724.","DOI":"10.1057\/jors.2013.71"},{"key":"key2020122723141956000_b6","doi-asserted-by":"crossref","unstructured":"Burke, E.K. , Hyde, M. and Kendall, G. (2006), \u201cEvolving bin packing heuristics with genetic programming\u201d, Proceedings of PPSN IX, Springer-Verlag, pp. 860-869.","DOI":"10.1007\/11844297_87"},{"key":"key2020122723141956000_b7","doi-asserted-by":"crossref","unstructured":"Burke, E.K. , Hyde, M. and Kendall, G. (2012), \u201cGrammatical evolution of local search Heuristics\u201d, IEEE Transactions on Evolutionary Computation , Vol. 16 No. 3, pp. 406-417.","DOI":"10.1109\/TEVC.2011.2160401"},{"key":"key2020122723141956000_b8","doi-asserted-by":"crossref","unstructured":"Burke, E.K. , Hyde, M. , Kendall, G. , Ochoa, G. , \u00d6zcan, E. and Woodward, J. (2009), \u201cExploring Hyper-heuristic Methodologies with Genetic Programming\u201d, Computational Intelligence: Collaboration, Fusion and Emergence, Springer-Verlag, pp. 177-201.","DOI":"10.1007\/978-3-642-01799-5_6"},{"key":"key2020122723141956000_b9","doi-asserted-by":"crossref","unstructured":"Burke, E.K. , Hyde, M. , Kendall, G. , Ochoa, G. , \u00d6zcan, E. and Woodward, J. (2010a), \u201cA Classification of Hyper-heuristics Approaches\u201d, in Gendreau, M. and Potvin, J.-Y. (Eds), Handbook of Metaheuristics , pp. 449-468.","DOI":"10.1007\/978-1-4419-1665-5_15"},{"key":"key2020122723141956000_b10","doi-asserted-by":"crossref","unstructured":"Burke, E.K. , Hyde, M. , Kendall, G. and Woodward, J. (2010b), \u201cA genetic programming hyper-heuristic approach for evolving 2-d strip packing heuristics\u201d, IEEE Transactions on Evolutionary Computation , Vol. 14 No. 6, pp. 942-958.","DOI":"10.1109\/TEVC.2010.2041061"},{"key":"key2020122723141956000_b11","doi-asserted-by":"crossref","unstructured":"Burke, E.K. , Hyde, M. , Kendall, G. and Woodward, J. (2011), \u201cAutomating the packing heuristic design process with genetic programming\u201d, Evolutionary Computation , Vol. 20 No. 1, pp. 63-89.","DOI":"10.1162\/EVCO_a_00044"},{"key":"key2020122723141956000_b12","doi-asserted-by":"crossref","unstructured":"Burke, E.K. , Woodward, J. , Hyde, M. and Kendall, G. (2007), \u201cAutomatic heuristic generation with genetic programming: Evolving a jack-of-all trades or a master of one\u201d, in GECCO 2007, pp. 7-11.","DOI":"10.1145\/1276958.1277273"},{"key":"key2020122723141956000_b13","doi-asserted-by":"crossref","unstructured":"Chu, P.C. and Beasley, J.E. (1998), \u201cA genetic algorithm for the multidimensional knapsack problem\u201d, Journal of Heuristics , Vol. 4 No. 1, pp. 63-86.","DOI":"10.1023\/A:1009642405419"},{"key":"key2020122723141956000_b14","doi-asserted-by":"crossref","unstructured":"Cowling, P. , Kendall, G. and Soubeiga, E. (2001), \u201cA hyperheuristic approach to scheduling a sales summit\u201d, Proceedings of PATAT 2000, Springer-Verlag, pp. 176-190.","DOI":"10.1007\/3-540-44629-X_11"},{"key":"key2020122723141956000_b15","unstructured":"Denzinger, J. , Fuchs, M. and Fuchs, M. (1996), \u201cHigh performance atp systems by combining several ai methods\u201d, Technical report, SEKI-Report SR-96-09, University of Kaiserslautern."},{"key":"key2020122723141956000_b16","doi-asserted-by":"crossref","unstructured":"Drake, J.H. , Kililis, N. and \u00d6zcan, E. (2013), \u201cGeneration of VNS Components with Grammatical Evolution for Vehicle Routing\u201d, in Genetic Programming (EuroGP 2013), Springer Lecture Notes in Computer Science, Volume 7831, pp. 25-36.","DOI":"10.1007\/978-3-642-37207-0_3"},{"key":"key2020122723141956000_b17","unstructured":"Drake, J.H. , \u00d6zcan, E. and Burke, E.K. (2011), \u201cControlling crossover in a selection hyper-heuristic framework\u201d, Technical Report No. NOTTCS-TR-SUB-1104181638-4244, School of Computer Science, University of Nottingham, Nottingham."},{"key":"key2020122723141956000_b18","doi-asserted-by":"crossref","unstructured":"Drexl, A. (1988), \u201cA simulated annealing approach to the multiconstraint zero-one knapsack problem\u201d, Computing , Vol. 40 No. 1, pp. 1-8.","DOI":"10.1007\/BF02242185"},{"key":"key2020122723141956000_b19","doi-asserted-by":"crossref","unstructured":"Everett, H. (1963), \u201cGeneralized lagrange multiplier method for solving problems of optimum allocation of resources\u201d, Operations Research , Vol. 11 No. 3, pp. 399-417.","DOI":"10.1287\/opre.11.3.399"},{"key":"key2020122723141956000_b20","unstructured":"Fisher, M. and Thompson, G. (1961), \u201cProbabilistic learning combinations of local job-shop scheduling rules\u201d, Factory Scheduling Conference, Carnegie Institute of Technology, May 10-12."},{"key":"key2020122723141956000_b21","doi-asserted-by":"crossref","unstructured":"Fr\u00e9ville, A. (2004), \u201cThe multidimensional 0-1 knapsack problem: An overview\u201d, EJOR , Vol. 155 No. 1, pp. 1-21.","DOI":"10.1016\/S0377-2217(03)00274-1"},{"key":"key2020122723141956000_b22","doi-asserted-by":"crossref","unstructured":"Fr\u00e9ville, A. and Plateau, G. (1994), \u201cAn efficient preprocessing procedure for the multidimensional 0-1 knapsack problem\u201d, Discrete Applied Mathematics , Vol. 49 Nos 1-3, pp. 189-212.","DOI":"10.1016\/0166-218X(94)90209-7"},{"key":"key2020122723141956000_b23","doi-asserted-by":"crossref","unstructured":"Fukunaga, A.S. (2008), \u201cAutomated discovery of local search heuristics for satisfiability testing\u201d, Evolutionary Computation , Vol. 16 No. 1, pp. 31-61.","DOI":"10.1162\/evco.2008.16.1.31"},{"key":"key2020122723141956000_b24","unstructured":"Garey, M.R. and Johnson, D.S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , W. H. Freeman & Co, New York, NY."},{"key":"key2020122723141956000_b25","doi-asserted-by":"crossref","unstructured":"Geiger, C.D. , Uzsoy, R. and Aytug, H. (2006), \u201cRapid modelling and discovery of priority dispatching rules: An autonomous learning approach\u201d, Journal of Scheduling , Vol. 9 No. 1, pp. 7-34.","DOI":"10.1007\/s10951-006-5591-8"},{"key":"key2020122723141956000_b26","doi-asserted-by":"crossref","unstructured":"Glover, F. and Kochenberger, G. (1996), \u201cCritical event tabu search for multidimensional knapsack problems\u201d, in Osman, I.H. and Kelly, J.P. (Eds), Meta-Heuristics: Theory & Applications , Kluwer Academic Publishers, pp. 407-427.","DOI":"10.1007\/978-1-4613-1361-8_25"},{"key":"key2020122723141956000_b27","doi-asserted-by":"crossref","unstructured":"Hanafi, S. and Fr\u00e9ville, A. (1998), \u201cAn efficient tabu search approach for the 0-1 multidimensional knapsack problem\u201d, EJOR , Vol. 106 Nos 2-3, pp. 659-675.","DOI":"10.1016\/S0377-2217(97)00296-8"},{"key":"key2020122723141956000_b28","doi-asserted-by":"crossref","unstructured":"Hauptman, A. , Elyasaf, A. and Sipper, M. (2010), \u201cEvolving hyper heuristic-based solvers for rush hour and freecell\u201d, Proceedings of SOCS 2010, pp. 149-150.","DOI":"10.1609\/socs.v1i1.18150"},{"key":"key2020122723141956000_b29","doi-asserted-by":"crossref","unstructured":"Hembecker, F. , Lopes H.S., and Godoy, .W. Jr (2007), \u201cParticle swarm optimization for the multidimensional knapsack problem\u201d, Proceedings of ICANNGA 2007, Springer-Verlag, Berlin, Heidelberg, pp. 358-365.","DOI":"10.1007\/978-3-540-71618-1_40"},{"key":"key2020122723141956000_b30","unstructured":"Hyde, M. , \u00d6zcan, E. and Burke, E.K. (2009), \u201cMultilevel search for evolving the acceptance criteria of a hyper-heuristic\u201d, MISTA 2009, pp. 798-801."},{"key":"key2020122723141956000_b31","doi-asserted-by":"crossref","unstructured":"Keller, R.E. and Poli, R. (2007), \u201cLinear genetic programming of parsimonious metaheuristics\u201d, Proceedings of CEC 2007, pp. 4508-4515.","DOI":"10.1109\/CEC.2007.4425062"},{"key":"key2020122723141956000_b32","unstructured":"Khuri, S. , Back, T. and Heitkotter, J. (1994), \u201cThe 0\/1 multiple knapsack problem and genetic algorithms\u201d, Proceedings of SAC 1994, ACM, New York, NY, pp. 188-193."},{"key":"key2020122723141956000_b33","unstructured":"Koza, J.R. (1992), Genetic programming: on the programming of computers by means of natural selection , The MIT Press, Cambridge, MA."},{"key":"key2020122723141956000_b34","doi-asserted-by":"crossref","unstructured":"Kumar, R. , Joshi, A.H. , Banka, K.K. and Rockett, P.I. (2008), \u201cEvolution of hyperheuristics for the biobjective 0\/1 knapsack problem by multiobjective genetic programming\u201d, Proceedings of GECCO 2008, pp. 1227-1234.","DOI":"10.1145\/1389095.1389335"},{"key":"key2020122723141956000_b35","doi-asserted-by":"crossref","unstructured":"Lorie, J. and Savage, L. (1955), \u201cThree problems in capital rationing\u201d, Journal of Business , Vol. 28 No. 4, pp. 229-239.","DOI":"10.1086\/294081"},{"key":"key2020122723141956000_b36","doi-asserted-by":"crossref","unstructured":"Magazine, M.J. and Oguz, O. (1984), \u201cA heuristic algorithm for the multidimensional zero-one knapsack problem\u201d, EJOR , Vol. 16 No. 3, pp. 319-326.","DOI":"10.1016\/0377-2217(84)90286-8"},{"key":"key2020122723141956000_b37","doi-asserted-by":"crossref","unstructured":"Mansini, R. and Speranza, M.G. (2011), \u201cCoral: An exact algorithm for the multidimensional knapsack problem\u201d, INFORMS J. on Computing , Vol. 23 No. 3, pp. 399-415.","DOI":"10.1287\/ijoc.1110.0460"},{"key":"key2020122723141956000_b38","doi-asserted-by":"crossref","unstructured":"Ohlsson, M. , Peterson, C. and Soderberg, B. (1993), \u201cNeural networks for optimization problems with inequality constraints: the knapsack problem\u201d, Neural Comput , Vol. 5 No. 2, pp. 331-339.","DOI":"10.1162\/neco.1993.5.2.331"},{"key":"key2020122723141956000_b39","doi-asserted-by":"crossref","unstructured":"\u00d6zcan, E. and Ba\u015faran, C. (2009), \u201cA case study of memetic algorithms for constraint optimization\u201d, Soft Computing , Vol. 13 Nos 8-9, pp. 871-882.","DOI":"10.1007\/s00500-008-0354-4"},{"key":"key2020122723141956000_b40","doi-asserted-by":"crossref","unstructured":"\u00d6zcan, E. , Bilgin, B. and Korkmaz, E. (2008), \u201cA comprehensive analysis of hyper-heuristics\u201d, Intelligent Data Analysis , Vol. 12 No. 1, pp. 3-23.","DOI":"10.3233\/IDA-2008-12102"},{"key":"key2020122723141956000_b41","doi-asserted-by":"crossref","unstructured":"Petersen, C. (1967), \u201cComputational experience with variants of the balas algorithm applied to the selection of r&d projects\u201d, Management Science , Vol. 13 No. 9, pp. 736-750.","DOI":"10.1287\/mnsc.13.9.736"},{"key":"key2020122723141956000_b42","doi-asserted-by":"crossref","unstructured":"Pirkul, H. (1987), \u201cA heuristic solution procedure for the multiconstraint zero-one knapsack problem\u201d, Naval Research Logistics , Vol. 34 No. 2, pp. 161-172.","DOI":"10.1002\/1520-6750(198704)34:2<161::AID-NAV3220340203>3.0.CO;2-A"},{"key":"key2020122723141956000_b43","unstructured":"Qian, F. and Ding, R. (2007), \u201cSimulated annealing for the 0\/1 multidimensional knapsack problem\u201d, Numerical Mathematics , Vol. 16 No. 4, pp. 320-327."},{"key":"key2020122723141956000_b44","doi-asserted-by":"crossref","unstructured":"Ross, P. (2005), \u201cHyper-heuristics\u201d, in Burke, E.K. and Kendall, G. (Eds), Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques , Springer, pp. 529-556.","DOI":"10.1007\/0-387-28356-0_17"},{"key":"key2020122723141956000_b45","doi-asserted-by":"crossref","unstructured":"Senju, S. and Toyoda, Y. (1968), \u201cAn approach to linear programming with 0-1 variables\u201d, Management Science , Vol. 15 No. 4, pp. 196-207.","DOI":"10.1287\/mnsc.15.4.B196"},{"key":"key2020122723141956000_b46","doi-asserted-by":"crossref","unstructured":"Vimont, Y. , Boussier, S. and Vasquez, M. (2008), \u201cReduced costs propagation in an efficient implicit enumeration for the 0-1 multidimensional knapsack problem\u201d, J. of Combinatorial Opt. , Vol. 15 No. 2, pp. 165-178.","DOI":"10.1007\/s10878-007-9074-4"},{"key":"key2020122723141956000_b47","doi-asserted-by":"crossref","unstructured":"Volgenant, A. and Zoon, J.A. (1990), \u201cAn improved heuristic for multidimensional 0-1 knapsack problems\u201d, Journal of the Operational Research Society , Vol. 41 No. 1, pp. 963-970.","DOI":"10.1057\/jors.1990.148"}],"container-title":["Kybernetes"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.emeraldinsight.com\/doi\/full-xml\/10.1108\/K-09-2013-0201","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.emerald.com\/insight\/content\/doi\/10.1108\/K-09-2013-0201\/full\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.emerald.com\/insight\/content\/doi\/10.1108\/K-09-2013-0201\/full\/html","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T21:50:00Z","timestamp":1753393800000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.emerald.com\/k\/article\/43\/9-10\/1500-1511\/267535"}},"subtitle":[],"editor":[{"given":"Ranulph","family":"Glanville","sequence":"first","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"David","family":"Griffiths","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Philip","family":"Baron","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2014,11,3]]},"references-count":47,"journal-issue":{"issue":"9\/10","published-print":{"date-parts":[[2014,11,3]]}},"alternative-id":["10.1108\/K-09-2013-0201"],"URL":"https:\/\/doi.org\/10.1108\/k-09-2013-0201","relation":{},"ISSN":["0368-492X"],"issn-type":[{"value":"0368-492X","type":"print"}],"subject":[],"published":{"date-parts":[[2014,11,3]]}}}