Evolving Bin Packing Heuristics with Genetic Programming
The DOI matches its Crossref record; 32 of the 34 references it cites were found in a registry or an index.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Indeed, like FunSearch, hyper-heuristics have also been applied to online bin packing, with the learned heuristics able to match the performance of first fit82 and best fit83 on a set of generated bin packing instances.”
From Mathematical discoveries from program search with large language models (2024) · cites this paper as [82]
Citations
Cites
(1979) · Cited by 43,841
No free lunch theorems for optimization
Wolpert, D. H., & Macready, W. G. (1997) · IEEE Transactions on Evolutionary Computation · doi:10.1109/4235.585893 · Cited by 14,237 · cited 1×
“Of course, the No Free Lunch theorem [7,8] shows that all search algorithms have the same average performance on all problems defined on a given finite search space.”
BackgroundGenetic Programming: On the Programming of Computers by Means of Natural Selection
Koza, J. R. (1992) · Medical Entomology and Zoology · Cited by 13,082
(2003) · International Series in Operations Research & Management Science · doi:10.1007/b101874 · Cited by 3,430
Knapsack Problems: Algorithms and Computer Implementations
Connolly, D., Martello, S., & Toth, P. (1991) · Journal of the Operational Research Society · doi:10.2307/2583458 · Cited by 3,120 · cited 1×
“In other words, the set of integers must be divided into the smallest number of subsets so that the sum of the sizes of the pieces in a subset does not exceed C [18].”
BackgroundGenetic programming II: Automatic discovery of reusable programs
(1995) · Computers & Mathematics with Applications · doi:10.1016/0898-1221(95)90099-3 · Cited by 1,901
Knapsack problems, algorithms and computer implementations
De Kort, J. (1991) · European Journal of Operational Research · doi:10.1016/0377-2217(91)90159-s · Cited by 1,402
Handbook of Combinatorial Optimization
(1999) · Springer eBooks · doi:10.1007/978-1-4757-3023-4 · Cited by 1,216
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
Johnson, D. S., Demers, A., Ullman, J. D., Garey, M. R., & Graham, R. L. (1974) · SIAM Journal on Computing · doi:10.1137/0203025 · Cited by 911
(2005) · doi:10.1007/0-387-28356-0 · Cited by 853
Self-citationGenetic Programming III: Darwinian Invention and Problem Solving
Koza, J. R., André, D., Bennett, F. H., & Keane, M. A. (1999) · Medical Entomology and Zoology · Cited by 763
Hyper-Heuristics: An Emerging Direction in Modern Search Technology
Burke, E., Kendall, G., Newall, J., Hart, E., Ross, P., & Schulenburg, S. (2006) · International Series in Operations Research & Management Science · doi:10.1007/0-306-48056-5_16 · Cited by 665 · cited 2×
“One of the aims of a hyper-heuristic [4,5] is to “raise the level of generality at which optimisation systems can operate” [5].”
BackgroundSelf-citationA hybrid grouping genetic algorithm for bin packing
Falkenauer, E. (1996) · Journal of Heuristics · doi:10.1007/bf00226291 · Cited by 601 · cited 1×
“Twenty instances of the bin packing problem are used in this research, taken from benchmark data studied by Falkenauer in [19] and now maintained by Beasley in the OR-Library of Brunel University [20].”
MethodGenetic Programming II: Automatic Discovery of Reusable Programs.
O'Reilly, U.-M. (1994) · Artificial Life · doi:10.1162/artl.1994.1.4.439 · Cited by 546 · cited 1×
“In this work we use a basic genetic programming system which does not incorporate any of the more advanced techniques such as re-usable code, loops, or memory, all of which are explained in [1] and [2] for the interested reader.”
MethodA Tabu-Search Hyperheuristic for Timetabling and Rostering
Burke, E. K., Kendall, G., & Soubeiga, E. (2003) · Journal of Heuristics · doi:10.1023/b:heur.0000012446.94732.b6 · Cited by 509 · cited 2×
“[12]), hyper-heuristics have had their low-level heuristics given to them by the human programmer, and so the number and quality of heuristics that the hyper-heuristic has available is limited to those which a human can provide.”
BackgroundMethodSelf-citationA graph-based hyper-heuristic for educational timetabling problems
Burke, E. K., McCollum, B., Meisels, A., Petrovic, S., & Qu, R. (2007) · European Journal of Operational Research · doi:10.1016/j.ejor.2005.08.012 · Cited by 507 · cited 1×
“A graph based hyperheuristic is used for timetabling in [15].”
MethodSelf-citationGenetic Programming III - Darwinian Invention and Problem Solving
Nordin, P. (1999) · Evolutionary Computation · doi:10.1162/evco.1999.7.4.451 · Cited by 501 · cited 2×
“In this work we use a basic genetic programming system which does not incorporate any of the more advanced techniques such as re-usable code, loops, or memory, all of which are explained in [1] and [2] for the interested reader.”
BackgroundMethodA Hyperheuristic Approach to Scheduling a Sales Summit
Cowling, P., Kendall, G., & Soubeiga, E. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44629-x_11 · Cited by 475 · cited 1×
“A choice function has also been employed as a hyper-heuristic, to rank the low-level heuristics and choose the best [13].”
MethodSelf-citationA genetic algorithm for bin packing and line balancing
Falkenauer, E., & Delchambre, A. (2003) · Proceedings 1992 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1992.220088 · Cited by 279 · cited 1×
“An example is given in [27], where, if the number of bins used in both situations is equal, a solution with some full bins and some almost empty bins is considered superior to a solution where all bins are packed to a constant level.”
BackgroundCase-based heuristic selection for timetabling problems
Burke, E. K., Petrovic, S., & Qu, R. (2006) · Journal of Scheduling · doi:10.1007/s10951-006-6775-y · Cited by 223 · cited 1×
“Case based heuristic selection is applied on a timetabling problem in [16].”
MethodSelf-citationKoza, J. R., & Poli, R. (2006) · Search Methodologies · doi:10.1007/0-387-28356-0_5 · Cited by 216
Practice and Theory of Automated Timetabling III
Burke, E. K., & Erben, W. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44629-x · Cited by 175
Self-citationBin Packing Approximation Algorithms: Combinatorial Analysis
Coffman, E. G., Galambos, G., Martello, S., & Vigo, D. (1999) · Springer eBooks · doi:10.1007/978-1-4757-3023-4_3 · Cited by 145 · cited 5×
“For example when items come off a production line and are placed into containers, or packages of different sizes are packed into trucks at a depot, and only a certain number of trucks can be at the depot at any one time [21].”
BackgroundInfluentialHyper-heuristics: Learning To Combine Simple Heuristics In Bin-packing Problems
Ross, P. D., Schulenburg, S., Marín-Blázquez, J. G., & Hart, E. (2002) · Edinburgh Napier Research Repository (Edinburgh Napier University) · Cited by 136
Ross, P. D. (2006) · Springer eBooks · doi:10.1007/0-387-28356-0_17 · Cited by 134
Ross, P. D., Marín-Blázquez, J. G., Schulenburg, S., & Hart, E. (2003) · Lecture notes in computer science · doi:10.1007/3-540-45110-2_5 · Cited by 98 · cited 1×
“Two hyper-heuristic methods have been tested on the one-dimensional bin-packing problem, a learning classifier system [9] and a genetic algorithm [10].”
MethodMulti-Objective Hyper-Heuristic Approaches for Space Allocation and Timetabling
Burke, E. K., Silva, J. D. L., & Soubeiga, E. (2005) · Springer eBooks · doi:10.1007/0-387-25383-1_6 · Cited by 83 · cited 1×
“A multi-objective hyper-heuristic is applied to space allocation and timetabling in [14].”
MethodSelf-citationDevelopment and application of hyperheuristics to personnel scheduling
Soubeiga, E. (2003) · Nottingham ePrints (University of Nottingham) · Cited by 72
An Ant Algorithm Hyperheuristic for the Project Presentation Scheduling Problem
Burke, E., Kendall, G., Landa-Silva, D., O'Brien, R. F. J., & Soubeiga, E. (2005) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2005.1554976 · Cited by 66 · cited 1×
“In [11], an ant algorithm hyper-heuristic chooses a sequence of low-level heuristics for the project presentation scheduling problem.”
MethodSelf-citationComplexity Theory and the No Free Lunch Theorem
Whitley, D., & Watson, J. P. (2006) · Springer eBooks · doi:10.1007/0-387-28356-0_11 · Cited by 57 · cited 1×
“Of course, the No Free Lunch theorem [7,8] shows that all search algorithms have the same average performance on all problems defined on a given finite search space.”
BackgroundOn Line Bin Packing with Items of Random Size
Rhee, W. T., & Talagrand, M. (1993) · Mathematics of Operations Research · doi:10.1287/moor.18.2.438 · Cited by 38 · cited 1×
“A number of examples of heuristics used in the online bin packing problem are described below: Best Fit [23]: Puts the piece in the fullest bin that has room for it.”
MethodMultiobjective parsimony enforcement for superior generalisation performance
Bernstein, Y., Li, X., Ciesielski, V., & Song, A. (2004) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2004.1330841 · Cited by 22 · cited 1×
“This plateau in the search space also means that code-bloat [26] was not an issue in the runs which produced Figs.”
Background
Research works printed but not linked: 1
- Dowsland, K., Soubeiga, E., Burke, E.K.: A simulated annealing hyper-heuristic for determining shipper sizes. European Journal of Operational Research (in press, to appear 2006, available online November 29, 2005) (accepted)
Cited by
A Field Guide to Genetic Programming
Poli, R., Langdon, W. B., & McPhee, N. F. (2008) · Cited by 1,930
Hyper-heuristics: a survey of the state of the art
Burke, E. K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., & Qu, R. (2013) · Journal of the Operational Research Society · doi:10.1057/jors.2013.71 · Cited by 1,263
Self-citationA Classification of Hyper-heuristic Approaches
Burke, E. K., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., & Woodward, J. R. (2010) · International Series in Operations Research & Management Science · doi:10.1007/978-1-4419-1665-5_15 · Cited by 563
“An alternative idea is to use genetic programming to evolve a program representing a function, which is part of the processing of a given problem specific construction heuristic [9, 8, 11, 22, 31, 59].”
BackgroundMethodInfluentialSelf-citationMathematical discoveries from program search with large language models
Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, F. J. R., Ellenberg, J. S., Wang, P., Fawzi, O., et al. (2024) · Nature · doi:10.1038/s41586-023-06924-6 · Cited by 544
“Indeed, like FunSearch, hyper-heuristics have also been applied to online bin packing, with the learned heuristics able to match the performance of first fit 82 and best fit 83 on a set of generated bin packing instances.”
MethodBin packing and cutting stock problems: Mathematical models and exact algorithms
Delorme, M., Iori, M., & Martello, S. (2016) · European Journal of Operational Research · doi:10.1016/j.ejor.2016.04.030 · Cited by 379
Metadata
- Authors
- Burke, E. K., Hyde, M. R., & Kendall, G.
- Affiliations
- University of Nottingham (GB)
- ORCID
- Kendall, G.
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg
- Published
- 2006
- Pages
- 860-869
- ISSN
- 0302-9743 (ISSN-L)
- 1611-3349
- OpenAlex
- W1820078070
- Cited by
- 144
- References
- 34
- Citations by year
- 2026: 3 · 2025: 3 · 2024: 3 · 2023: 5 · 2022: 7 · 2021: 5 · 2020: 10 · 2019: 5 · 2018: 4 · 2017: 8 · 2016: 5 · 2015: 2 · 2014: 9 · 2013: 13 · 2012: 11
- FWCI
- 24.87
- Type
- conference paper
- Language
- en
- Open access
- closed
- Licence
- www.springer.com/tdm (tdm)
- www.springer.com/tdm (vor)
- Locations
- Lecture notes in computer science (publishedVersion)
- Topics
- Physical Sciences › Engineering › Industrial and Manufacturing Engineering › Optimization and Packing Problems
- Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
- Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
- Keywords
- bin packing, genetic programming, heuristic evolution, NP-hard optimization, automated heuristic design, bin packing heuristics
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.