The DOI matches its Crossref record; 87 of the 87 references it cites were found in a registry or an index.
Bin packing and cutting stock problems: Mathematical models and exact algorithms
Open accessAbstract
We review the most important mathematical models and algorithms developed for the exact solution of the one-dimensional bin packing and cutting stock problems, and experimentally evaluate, on state-of-the art computers, the performance of the main available software tools.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
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
Self-citationApproximation Algorithms for NP-Hard Problems
(1997) · ACM SIGACT News · doi:10.1145/261342.571216 · Cited by 3,103
Decomposition Principle for Linear Programs
Dantzig, G. B., & Wolfe, P. (1960) · Operations Research · doi:10.1287/opre.8.1.101 · Cited by 2,315
A Linear Programming Approach to the Cutting-Stock Problem
Gilmore, P. C., & Gomory, R. E. (1961) · Operations Research · doi:10.1287/opre.9.6.849 · Cited by 2,024
OR-Library: Distributing Test Problems by Electronic Mail
Beasley, J. E. (1990) · Journal of the Operational Research Society · doi:10.1057/jors.1990.166 · Cited by 1,899
Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2019
Auger, A., & Stützle, T. (2019) · Dépôt institutionnel de l'Université libre de Bruxelles (Université Libre de Bruxelles) · Cited by 1,749
Graham, R., Grötschel, M., & Lovász, L. (1995) · Medical Entomology and Zoology · Cited by 1,526
A typology of cutting and packing problems
Dyckhoff, H. (1990) · European Journal of Operational Research · doi:10.1016/0377-2217(90)90350-k · Cited by 1,125
A Linear Programming Approach to the Cutting Stock Problem—Part II
Gilmore, P. C., & Gomory, R. E. (1963) · Operations Research · doi:10.1287/opre.11.6.863 · Cited by 1,119
Selected Topics in Column Generation
Lübbecke, M. E., & Desrosiers, J. (2005) · Operations Research · doi:10.1287/opre.1050.0234 · Cited by 1,102
Proceedings 35th Annual Symposium on Foundations of Computer Science
(1994) · doi:10.1109/sfcs.1994 · Cited by 1,087
Proceedings 1992 IEEE International Conference on Robotics and Automation
(1992) · doi:10.1109/robot.1992 · Cited by 1,084
Mathematical Methods of Organizing and Planning Production
Kantorovich, L. V. (1960) · Management Science · doi:10.1287/mnsc.6.4.366 · Cited by 1,082
Approximation algorithms for bin packing: a survey
Coffman, E. G., Garey, M. R., & Johnson, D. S. (1996) · PWS Publishing Co. eBooks · Cited by 862
Two-dimensional packing problems: A survey
Lodi, A., Martello, S., & Monaci, M. (2002) · European Journal of Operational Research · doi:10.1016/s0377-2217(02)00123-6 · Cited by 843
Self-citationMultistage Cutting Stock Problems of Two and More Dimensions
Gilmore, P. C., & Gomory, R. E. (1965) · Operations Research · doi:10.1287/opre.13.1.94 · Cited by 809
Edmonds polytopes and a hierarchy of combinatorial problems
Chvátal, V. (1973) · Discrete Mathematics · doi:10.1016/0012-365x(73)90167-2 · Cited by 624
A hybrid grouping genetic algorithm for bin packing
Falkenauer, E. (1996) · Journal of Heuristics · doi:10.1007/bf00226291 · Cited by 601
Near-optimal bin packing algorithms
Johnson, D. S. (1973) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 573
50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art
(2010) · Springer eBooks · doi:10.1007/978-3-540-68279-0 · Cited by 534
An efficient approximation scheme for the one-dimensional bin-packing problem
Karmarkar, N. K., & Karp, R. M. (1982) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1982.61 · Cited by 491
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence
Ma, W., Luo, X., & Liu, W. (2014) · National Conference on Artificial Intelligence · Cited by 477
Approximation Algorithms for Bin-Packing — An Updated Survey
Coffman, E. G., Garey, M. R., & Johnson, D. S. (1984) · CISM International Centre for Mechanical Sciences · doi:10.1007/978-3-7091-4338-4_3 · Cited by 433
Recent advances on two-dimensional bin packing problems
Lodi, A., Martello, S., & Vigo, D. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00347-x · Cited by 328
Self-citationA Suggested Computation for Maximal Multi-Commodity Network Flows
Ford, L. R., & Fulkerson, D. R. (2004) · Management Science · doi:10.1287/mnsc.1040.0269 · Cited by 326
A Suggested Computation for Maximal Multi-Commodity Network Flows
Ford, L. R., & Fulkerson, D. R. (1958) · Management Science · doi:10.1287/mnsc.5.1.97 · Cited by 325
Exact solution of bin‐packing problems using column generation and branch‐and‐bound
de Carvalho, J. V. (1999) · Annals of Operations Research · doi:10.1023/a:1018952112615 · Cited by 300
Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem
Scholl, A., Klein, R., & Jürgens, C. (1997) · Computers & Operations Research · doi:10.1016/s0305-0548(96)00082-2 · Cited by 295
Handbook of Combinatorial Optimization
Pardalos, P. M., Du, D., & Graham, R. L. (2013) · Springer eBooks · doi:10.1007/978-1-4419-7997-1 · Cited by 294
Handbook of Combinatorial Optimization: Volume1–3
(1998) · Springer eBooks · doi:10.1007/978-1-4613-0303-9 · Cited by 292
Vanderbeck, F. (2000) · Operations Research · doi:10.1287/opre.48.1.111.12453 · Cited by 291
Lower bounds and reduction procedures for the bin packing problem
Martello, S., & Toth, P. (1990) · Discrete Applied Mathematics · doi:10.1016/0166-218x(90)90094-s · Cited by 291
Self-citationBin Packing Approximation Algorithms: Survey and Classification
Coffman, E. G., Csirik, J., Galambos, G., Martello, S., & Vigo, D. (2013) · Handbook of Combinatorial Optimization · doi:10.1007/978-1-4419-7997-1_35 · Cited by 289
Self-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
Cutting and Packing Problems: A Categorized, Application-Orientated Research Bibliography
Sweeney, P., & Paternoster, E. R. (1992) · Journal of the Operational Research Society · doi:10.1057/jors.1992.101 · Cited by 236
Solving binary cutting stock problems by column generation and branch-and-bound
Vance, P. H., Barnhart, C., Johnson, E. L., & Nemhauser, G. L. (1994) · Computational Optimization and Applications · doi:10.1007/bf01300970 · Cited by 226
Mixed Integer Programming: Analyzing 12 Years of Progress
Achterberg, T., & Wunderling, R. (2013) · Facets of Combinatorial Optimization · doi:10.1007/978-3-642-38189-8_18 · Cited by 220
Ant colony optimization and local search for bin packing and cutting stock problems
Levine, J., & Ducatelle, F. (2004) · Journal of the Operational Research Society · doi:10.1057/palgrave.jors.2601771 · Cited by 211
New worst-case results for the bin-packing problem
Simchi‐Levi, D. (1994) · Naval Research Logistics (NRL) · doi:10.1002/1520-6750(199406)41:4<579::aid-nav3220410409>3.0.co;2-g · Cited by 209
Computational study of a column generation algorithm for bin packing and cutting stock problems
Vanderbeck, F. (1999) · Mathematical Programming · doi:10.1007/s101070050105 · Cited by 201
Heuristics for the integer one-dimensional cutting stock problem: A computational study
W�scher, G., & Gau, T. (1996) · OR Spectrum · doi:10.1007/bf01539705 · Cited by 189
Albers, S., & Marion, J.-Y. (2009) · Publication Server of Goethe University Frankfurt am Main (Goethe University Frankfurt) · doi:10.4230/lipics.stacs.2012.i · Cited by 171
Mixed Integer Programming Computation
Lodi, A. (2009) · Springer eBooks · doi:10.1007/978-3-540-68279-0_16 · Cited by 163
Branch-and-Price Algorithms for the One-Dimensional Cutting Stock Problem
Vance, P. H. (1998) · Computational Optimization and Applications · doi:10.1023/a:1018346107246 · Cited by 161
Bin 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
Self-citationEvolving Bin Packing Heuristics with Genetic Programming
Burke, E. K., Hyde, M. R., & Kendall, G. (2006) · Lecture Notes in Computer Science · doi:10.1007/11844297_87 · Cited by 144
Algorithm Design for Computer System Design
Ausiello, G., Lucertini, M., & Serafini, P. (1984) · Courses and lectures · doi:10.1007/978-3-7091-4338-4 · Cited by 138
Hyper-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
Approximation Algorithms for Bin Packing Problems: A Survey
Garey, M. R., & Johnson, D. S. (1981) · Springer eBooks · doi:10.1007/978-3-7091-2748-3_8 · Cited by 132
A Hybrid Improvement Heuristic for the One-Dimensional Bin Packing Problem
Alvim, A. C. F., Ribeiro, C. C., Glover, F., & Aloise, D. J. (2004) · Journal of Heuristics · doi:10.1023/b:heur.0000026267.44673.ed · Cited by 129
A grouping genetic algorithm with controlled gene transmission for the bin packing problem
Quiróz-Castellanos, M., Cruz–Reyes, L., Torres-Jiménez, J., Gomez-Santillan, C. G., Huacuja, H. J. F., & Alvim, A. C. F. (2014) · Computers & Operations Research · doi:10.1016/j.cor.2014.10.010 · Cited by 124
First Fit bin packing: A tight analysis
Dósa, G., & Sgall, J. (2013) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.stacs.2013.538 · Cited by 121
Capacitated Vehicle Routing on Trees
Labbé, M., Gilbert Laporte, A., & Mercure, H. (1991) · Operations Research · doi:10.1287/opre.39.4.616 · Cited by 119
Hybrid genetic algorithms for bin-packing and related problems
Reeves, C. R. (1996) · Annals of Operations Research · doi:10.1007/bf02125404 · Cited by 116
Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error
Jayram, T. S., & Woodruff, D. P. (2013) · ACM Transactions on Algorithms · doi:10.1145/2483699.2483706 · Cited by 114
The cutting stock problem and integer rounding
Marcotte, O. (1985) · Mathematical Programming · doi:10.1007/bf01582013 · Cited by 103
The Bin‐Packing Problem: A Problem Generator and Some Numerical Experiments with FFD Packing and MTP
Schwerin, P., & Wäscher, G. (1997) · International Transactions in Operational Research · doi:10.1111/j.1475-3995.1997.tb00093.x · Cited by 101
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
A new algorithm for optimal bin packing
Korf, R. E. (2002) · Cited by 93
Tight absolute bound for First Fit Decreasing bin-packing: FFD(L)⩽11/9 OPT(L)+6/9
Dósa, G., Li, R., Han, X., et al. (2013) · Theoretical Computer Science · doi:10.1016/j.tcs.2013.09.007 · Cited by 81
A Note on Bounding a Class of Linear Programming Problems, Including Cutting Stock Problems
Farley, A. (1990) · Operations Research · doi:10.1287/opre.38.5.922 · Cited by 79
Bin packing with items uniformly distributed over intervals [a,b]
Lueker, G. S. (1983) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1983.9 · Cited by 63
Approximating Bin Packing within O(log OPT · Log Log OPT) Bins
Rothvoß, T. (2013) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.11 · Cited by 63
Optimal Analysis of Best Fit Bin Packing
Dósa, G., & Sgall, J. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-43948-7_36 · Cited by 58
Two‐Dimensional Bin Packing Problems
Lodi, A., Martello, S., Monaci, M., & Vigo, D. (2014) · Wiley eBooks · doi:10.1002/9781119005353.ch5 · Cited by 55
Self-citationA histogram-matching approach to the evolution of bin-packing strategies
Poli, R., Woodward, J. R., & Burke, E. K. (2007) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2007.4424926 · Cited by 49
Bidimensional packing by bilinear programming
Caprara, A., & Monaci, M. (2007) · Mathematical Programming · doi:10.1007/s10107-007-0184-7 · Cited by 48
Optimal Integer Solutions to Industrial Cutting Stock Problems
Degraeve, Z., & Schrage, L. E. (1999) · INFORMS journal on computing · doi:10.1287/ijoc.11.4.406 · Cited by 47
Heuristic Solution of Open Bin Packing Problems
Gent, I. P. (1998) · Journal of Heuristics · doi:10.1023/a:1009678411503 · Cited by 45
An Improved Algorithm for Optimal Bin Packing
Korf, R. E. (2003) · Cited by 44
Analysis and Design of Algorithms in Combinatorial Optimization
Ausiello, G., & Lucertini, M. (1981) · Springer eBooks · doi:10.1007/978-3-7091-2748-3 · Cited by 43
Propagating the Bin Packing Constraint Using Linear Programming
Cambazard, H., & O’Sullivan, B. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15396-9_13 · Cited by 37
An analysis of lower bound procedures for the bin packing problem
Bourjolly, J.-M., & Rebetez, V. (2003) · Computers & Operations Research · doi:10.1016/s0305-0548(03)00244-2 · Cited by 25
Sim, K., & Hart, E. (2013) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/2463372.2463555 · Cited by 25
Osogami, T., & Okano, H. (2003) · Journal of Heuristics · doi:10.1023/a:1021837611236 · Cited by 23
Improved bin completion for optimal bin packing and number partitioning
Schreiber, E. L., & Korf, R. E. (2013) · Cited by 23
The optimal absolute ratio for online bin packing
Balogh, J., Békési, J., Dósa, G., Sgall, J., & van Stee, R. (2015) · Figshare · Cited by 21
Tight absolute bound for First Fit Decreasing bin-packing:
Dósa, G., Li, R., Han, X. H., et al. (2013) · Cited by 20
Two‐Dimensional Bin Packing Problems
Lodi, A., Martello, S., Monaci, M., & Vigo, D. (2013) · Wiley eBooks · doi:10.1002/9781118600207.ch5 · Cited by 18
Self-citationNature inspired genetic algorithms for hard packing problems
Rohlfshagen, P., & Bullinaria, J. A. (2008) · Annals of Operations Research · doi:10.1007/s10479-008-0464-5 · Cited by 14
A tight lower bound for optimal bin packing
Chao, H.-Y., Harper, M. P., & Quong, R. W. (1995) · Operations Research Letters · doi:10.1016/0167-6377(95)00041-0 · Cited by 13
An improved lower bound for the bin packing problem
Chen, B., & Srivastava, B. (1996) · Discrete Applied Mathematics · doi:10.1016/0166-218x(96)80459-8 · Cited by 12
A classification scheme for bin packing theory
Coffman, E. G., & Csirik, J. (2007) · Acta Cybernetica · Cited by 9
Consistency Check for the Bin Packing Constraint Revisited
Dupuis, J., Schaus, P., & Deville, Y. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13520-0_15 · Cited by 8
Cited by
Osaba, E., Villar-Rodriguez, E., Del Ser, J., Nebro, A. J., Molina, D., LaTorre, A., Suganthan, P. N., Coello Coello, C. A., & Herrera, F. (2021) · Swarm and Evolutionary Computation · doi:10.1016/j.swevo.2021.100888 · Cited by 406
Multiblock ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers
Gambella, C., & Simonetto, A. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3033139 · Cited by 60
Metadata
- Authors
- Delorme, M., Iori, M., & Martello, S.
- Venue
- European Journal of Operational Research
- Publisher
- Elsevier BV
- Published
- 2016-11
- Volume
- 255
- Issue
- 1
- Pages
- 1-20
- ISSN
- 0377-2217 (ISSN-L)
- OpenAlex
- W2342137734
- Cited by
- 379
- References
- 87
- FWCI
- 46.25
- Type
- journal article
- Language
- en
- Open access
- green
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.