Bin packing and cutting stock problems: Mathematical models and exact algorithms

Achterberg, 2013, Mixed integer programming: Analyzing 12 years of progress, 449 Alves, 2016 Alvim, 2004, A hybrid improvement heuristic for the one-dimensional bin packing problem, Journal of Heuristics, 10, 205, 10.1023/B:HEUR.0000026267.44673.ed Bai, 2012, A simulated annealing hyper-heuristic methodology for flexible decision support, 4OR, 10, 43, 10.1007/s10288-011-0182-8 Balas, 1965, An additive algorithm for solving linear programs with zero-one variables, Operations Research, 13, 517, 10.1287/opre.13.4.517 Balogh, 2015, The optimal absolute ratio for online bin packing, 1425 Beasley, 1990, OR-library: Distributing test problems by electronic mail, Journal of the Operational Research Society, 41, 1069, 10.1057/jors.1990.166 Beck, 1995, Discrepancy theory, 1405 Belov, 2003 Belov, 2002, A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths, European Journal of Operational Research, 141, 274, 10.1016/S0377-2217(02)00125-X Belov, 2006, A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting, European Journal of Operational Research, 171, 85, 10.1016/j.ejor.2004.08.036 Belov, 2008, Gomory cuts from a position-indexed formulation of 1D stock cutting, 3 Ben Amor, 2005, Cutting stock problems, 131 Ben Amor, 2006, Dual-optimal inequalities for stabilized column generation, Operations Research, 54, 454, 10.1287/opre.1060.0278 Berge, 1977, Coloring the edges of a hypergraph and linear programming techniques, Annals of Discrete Mathematics, 1, 65, 10.1016/S0167-5060(08)70727-1 Bhatia, 2004, Packing bins using multi-chromosomal genetic representation and better fit heuristic, 181 Bhatia, 2009, Better-fit heuristic for one-dimensional bin-packing problem, 193 Bourjolly, 2005, An analysis of lower bound procedures for the bin packing problem, Computers & Operations Research, 32, 395, 10.1016/S0305-0548(03)00244-2 Brandão, 2016, Bin packing and related problems: General arc-flow formulation with graph compression, Computers & Operations Research, 69, 56, 10.1016/j.cor.2015.11.009 Briant, 2008, Comparison of bundle and classical column generation, Mathematical Programming, 113, 299, 10.1007/s10107-006-0079-z Burke, 2006, Evolving bin packing heuristics with genetic programming, 860 Cambazard, 2010, Propagating the bin packing constraint using linear programming, 129 Caprara, 2014, Friendly bin packing instances without integer round-up property, Mathematical Programming, 150, 5, 10.1007/s10107-014-0791-z Caprara, 2009, Bidimensional packing by bilinear programming, Mathematical Programming, 118, 75, 10.1007/s10107-007-0184-7 Chan, 1998, Worst-case analyses, linear programming and the bin-packing problem, Mathematical Programming, 83, 213, 10.1007/BF02680559 Chao, 1995, A tight lower bound for optimal bin packing, Operations Research Letters, 18, 133, 10.1016/0167-6377(95)00041-0 Chen, 1996, An improved lower bound for the bin-packing problem, Discrete Applied Mathematics, 66, 81, 10.1016/0166-218X(96)80459-8 Chvátal, 1973, Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Mathematics, 4, 305, 10.1016/0012-365X(73)90167-2 Clautiaux, 2010, A survey of dual-feasible and superadditive functions, Annals of Operations Research, 179, 317, 10.1007/s10479-008-0453-8 Clautiaux, 2011, New stabilization procedures for the cutting stock problem, INFORMS Journal on Computing, 23, 530, 10.1287/ijoc.1100.0415 Coffman, 2007, A classification scheme for bin packing theory, Acta Cybernetica, 18, 47 Coffman, 2007, Performance guarantees for one-dimensional bin packing, 1 Coffman, 2013, Bin packing approximation algorithms: Survey and classification Coffman, E. G. Jr, Csirik, J., Johnson, D. S., & Woeginger, G. J. (2004). An introduction to bin packing. unpublished manuscript. Available at https://www.inf.u-szeged.hu/~csirik/ed5ut.pdf. Coffman, 1999, Bin packing approximation algorithms: Combinatorial analysis, 151 Coffman, 1984, Approximation algorithms for bin-packing – An updated survey, 49 Coffman, 1996, Approximation algorithms for bin packing: A survey, 46 Crainic, 2007, Computing the asymptotic worst-case of bin packing lower bounds, European Journal of Operational Research, 183, 1295, 10.1016/j.ejor.2005.07.032 Crainic, 2007, New bin packing fast lower bounds, Computers & Operations Research, 34, 3439, 10.1016/j.cor.2006.02.007 Dantzig, 1960, Decomposition principle for linear programs, Operations research, 8, 101, 10.1287/opre.8.1.101 Degraeve, 2003, Optimal integer solutions to industrial cutting-stock problems. Part 2. Benchmark results, INFORMS Journal on Computing, 15, 58, 10.1287/ijoc.15.1.58.15156 Degraeve, 1999, Optimal integer solutions to industrial cutting stock problems, INFORMS Journal on Computing, 11, 406, 10.1287/ijoc.11.4.406 Dell’Amico, 1995, Optimal scheduling of tasks on identical parallel processors, ORSA Journal on Computing, 7, 191, 10.1287/ijoc.7.2.191 Desaulniers, 2011, Cutting planes for branch-and-price algorithms, Networks, 58, 301, 10.1002/net.20471 Dósa, 2013, Tight absolute bound for first fit decreasing bin-packing: FFD(L) ≤ 11/9 OPT(L) + 6/9, Theoretical Computer Science, 510, 13, 10.1016/j.tcs.2013.09.007 Dósa, 2013, First fit bin packing: A tight analysis, 538 Dósa, 2014, Optimal analysis of best fit bin packing, 429 Dupuis, 2010, Consistency check for the bin packing constraint revisited, 117 Dyckhoff, 1981, A new linear programming approach to the cutting stock problem, Operations Research, 29, 1092, 10.1287/opre.29.6.1092 Dyckhoff, 1990, A typology of cutting and packing problems, European Journal of Operational Research, 44, 145, 10.1016/0377-2217(90)90350-K Dyckhoff, 1992 Eilon, 1971, The loading problem, Management Science, 17, 259, 10.1287/mnsc.17.5.259 Eisemann, 1957, The trim problem, Management Science, 3, 279, 10.1287/mnsc.3.3.279 Eisenbrand, 2013, Bin packing via discrepancy of permutations, ACM Transactions on Algorithms (TALG), 9, 1, 10.1145/2483699.2483704 Elhedhli, 2005, Ranking lower bounds for the bin packing problem, European Journal of Operational Research, 160, 34, 10.1016/j.ejor.2003.06.019 Elhedhli, 2015, Characterizing the optimality gap and the optimal packings for the bin packing problem, Optimization Letters, 9, 209, 10.1007/s11590-014-0789-8 Falkenauer, 1996, A hybrid grouping genetic algorithm for bin packing, Journal of Heuristics, 2, 5, 10.1007/BF00226291 Falkenauer, 1992, A genetic algorithm for bin packing and line balancing, 1186 Farley, 1990, A note on bounding a class of linear programming problems, including cutting stock problems, Operations Research, 38, 922, 10.1287/opre.38.5.922 Fekete, 2001, New classes of fast lower bounds for bin packing problems, Mathematical Programming, 91, 11, 10.1007/s101070100243 Fleszar, 2011, Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem, European Journal of Operational Research, 210, 176, 10.1016/j.ejor.2010.11.004 Fleszar, 2002, New heuristics for one-dimensional bin-packing, Computers & Operations Research, 29, 821, 10.1016/S0305-0548(00)00082-4 Ford, 1958, A suggested computation for maximal multi-commodity network flows, Management Science, 5, 97, 10.1287/mnsc.5.1.97 Gabrel, 2002, A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems, Operations Research Letters, 30, 252, 10.1016/S0167-6377(02)00124-4 Garey, 1979, Computers and intractability Garey, 1981, Approximation algorithms for bin-packing problems – A survey, 147 Gau, 1995, CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem, European Journal of Operational Research, 84, 572, 10.1016/0377-2217(95)00023-J Gent, 1998, Heuristic solution of open bin packing problems, Journal of Heuristics, 3, 299, 10.1023/A:1009678411503 Gilmore, 1961, A linear programming approach to the cutting-stock problem, Operations Research, 9, 849, 10.1287/opre.9.6.849 Gilmore, 1963, A linear programming approach to the cutting-stock problem, Operations Research, 11, 863, 10.1287/opre.11.6.863 Gilmore, 1965, Multistage cutting stock problems of two and more dimensions, Operations Research, 13, 94, 10.1287/opre.13.1.94 Gómez-Meneses, 2009, A hybrid extremal optimisation approach for the bin packing problem, 242 Goulimis, 1990, Optimal solutions for the cutting stock problem, European Journal of Operational Research, 44, 197, 10.1016/0377-2217(90)90355-F Gupta, 1999, A new heuristic algorithm for the one-dimensional bin-packing problem, Production Planning and Control, 10, 598, 10.1080/095372899232894 Haessler, 1975, Controlling cutting pattern changes in one dimensional trim problems, Operations Research, 23, 483, 10.1287/opre.23.3.483 Haessler, 1991, Cutting stock problems and solution procedures, European Journal of Operational Research, 54, 141, 10.1016/0377-2217(91)90293-5 Haouari, 2005, Fast lifting procedures for the bin packing problem, Discrete Optimization, 2, 201, 10.1016/j.disopt.2005.06.002 Holthaus, 2002, Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard lengths, European Journal of Operational Research, 141, 295, 10.1016/S0377-2217(02)00126-1 Jarboui, 2010, A new destructive bounding scheme for the bin packing problem, Annals of Operations Research, 179, 187, 10.1007/s10479-008-0459-2 Johnson, 1973 Kämpke, 1988, Simulated annealing: Use of a new tool in bin packing, Annals of Operations Research, 16, 327, 10.1007/BF02283751 Kantorovich, 1960, Mathematical methods of organizing and planning production, Management Science (English translation of a 1939 paper written in Russian), 6, 366 Kaparis, 2010, Separation algorithms for 0–1 knapsack polytopes, Mathematical Programming, 124, 69, 10.1007/s10107-010-0359-5 Karmarkar, 1982, An efficient approximation scheme for the one-dimensional bin-packing problem, 312 Kartak, 2004, Sufficient conditions for the integer round-up property to be violated for the linear cutting stock problem, Automation and Remote Control, 65, 407, 10.1023/B:AURC.0000019372.73750.3b Kartak, 2015, Minimal proper non-IRUP instances of the one-dimensional cutting stock problem, Discrete Applied Mathematics, 187, 120, 10.1016/j.dam.2015.02.020 Kim, 2010, Last two fit augmentation to the well-known construction heuristics for one-dimensional bin-packing problem: An empirical study, The International Journal of Advanced Manufacturing Technology, 50, 1145, 10.1007/s00170-010-2572-z Kiwiel, 2010, An inexact bundle approach to cutting-stock problems, INFORMS Journal on Computing, 22, 131, 10.1287/ijoc.1090.0326 Korf, 2002, A new algorithm for optimal bin packing, 731 Korf, 2003, An improved algorithm for optimal bin packing, 1252 Labbé, 1991, Capacitated vehicle routing on trees, Operations Research, 39, 616, 10.1287/opre.39.4.616 Levine, 2004, Ant colony optimization and local search for bin packing and cutting stock problems, Journal of the Operational Research Society, 55, 705, 10.1057/palgrave.jors.2601771 Lewis, 2009, A general-purpose hill-climbing method for order independent minimum grouping problems: A case study in graph colouring and bin packing, Computers & Operations Research, 36, 2295, 10.1016/j.cor.2008.09.004 Liang, 2002, A new evolutionary approach to cutting stock problems with and without contiguity, Computers & Operations Research, 29, 1641, 10.1016/S0305-0548(01)00039-9 Lodi, 2009, Mixed integer programming computation, 619 Lodi, 2002, Two-dimensional packing problems: A survey, European Journal of Operational Research, 141, 241, 10.1016/S0377-2217(02)00123-6 Lodi, 2010, Two-dimensional bin packing problems, Paradigms of Combinatorial Optimization: Problems and New Approaches, 2, 107 Lodi, 2002, Recent advances on two-dimensional bin packing problems, Discrete Applied Mathematics, 123, 379, 10.1016/S0166-218X(01)00347-X Loh, 2008, Solving the one-dimensional bin packing problem with a weight annealing heuristic, Computers & Operations Research, 35, 2283, 10.1016/j.cor.2006.10.021 López-Camacho, 2011, A hyper-heuristic for solving one and two-dimensional bin packing problems, 257 Lübbecke, 2005, Selected topics in column generation, Operations Research, 53, 1007, 10.1287/opre.1050.0234 Lueker, 1983, Bin packing with items uniformly distributed over intervals [a, b], 289 Lysgaard, 2004, A new branch-and-cut algorithm for the capacitated vehicle routing problem, Mathematical Programming, 100, 423, 10.1007/s10107-003-0481-8 Marcotte, 1985, The cutting stock problem and integer rounding, Mathematical Programming, 33, 82, 10.1007/BF01582013 Marcotte, 1986, An instance of the cutting stock problem for which the rounding property does not hold, Operations Research Letters, 4, 239, 10.1016/0167-6377(86)90009-X Martello, 1990 Martello, 1990, Lower bounds and reduction procedures for the bin packing problem, Discrete Applied Mathematics, 28, 59, 10.1016/0166-218X(90)90094-S Mukhacheva, 2000, Linear one-dimensional cutting-packing problems: Numerical experiments with the sequential value correction method (SVC) and a modified branch-and-bound method (MBB), Pesquisa Operacional, 20, 153, 10.1590/S0101-74382000000200002 Newman, 2012, Beck’s three permutations conjecture: A counterexample and some consequences, 253 Nitsche, 1999, Tighter relaxations for the cutting stock problem, European Journal of Operational Research, 112, 654, 10.1016/S0377-2217(97)00404-9 Osogami, 2003, Local search algorithms for the bin packing problem and their relationships to various construction heuristics, Journal of Heuristics, 9, 29, 10.1023/A:1021837611236 Poli, 2007, A histogram-matching approach to the evolution of bin-packing strategies, 3500 Quiroz-Castellanos, 2015, A grouping genetic algorithm with controlled gene transmission for the bin packing problem, Computers & Operations Research, 55, 52, 10.1016/j.cor.2014.10.010 Rao, 1976, On the cutting stock problem, Journal of the Computer Society of India, 7, 35 Reeves, 1996, Hybrid genetic algorithms for bin-packing and related problems, Annals of Operations Research, 63, 371, 10.1007/BF02125404 Rietz, 2008, Large gaps in one-dimensional cutting stock problems, Discrete Applied Mathematics, 156, 1929, 10.1016/j.dam.2007.08.052 Rohlfshagen, 2007, A genetic algorithm with exon shuffling crossover for hard bin packing problems, 1365 Rohlfshagen, 2010, Nature inspired genetic algorithms for hard packing problems, Annals of Operations Research, 179, 393, 10.1007/s10479-008-0464-5 Roodman, 1986, Near optimal solutions to one-dimensional cutting stock problem, Computers & Operations Research, 13, 713, 10.1016/0305-0548(86)90077-8 Ross, 2003, Learning a procedure that can solve hard bin-packing problems: A new GA-based approach to hyper-heuristics, 1295 Ross, 2002, Hyper-heuristics: Learning to combine simple heuristics in bin-packing problems, 942 Rothvoß, 2013, Approximating bin packing within O(log OPT * log log OPT) bins, 20 Ryan, 1981, An integer programming approach to scheduling, 269 Schaus, 2012, Cardinality reasoning for bin-packing constraint: Application to a tank allocation problem, 815 Scheithauer, 1995, A branch-and-bound algorithm for solving one-dimensional cutting stock problems exactly, Applications Mathematicae, 23, 151 Scheithauer, 1995, The modified integer round-up property of the one-dimensional cutting stock problem, European Journal of Operational Research, 84, 562, 10.1016/0377-2217(95)00022-I Scheithauer, 1997, Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem, Operations Research Letters, 20, 93, 10.1016/S0167-6377(96)00047-8 Scheithauer, 2001, Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm, Journal of the Operational Research Society, 52, 1390, 10.1057/palgrave.jors.2601242 Schoenfield, 2002 Scholl, 1997, Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem, Computers & Operations Research, 24, 627, 10.1016/S0305-0548(96)00082-2 Schreiber, 2013, Improved bin completion for optimal bin packing and number partitioning, 651 Schwerin, 1997, The bin-packing problem: A problem generator and some numerical experiments with FFD packing and MTP, International Transactions in Operational Research, 4, 377, 10.1111/j.1475-3995.1997.tb00093.x Schwerin, 1999, A new lower bound for the bin-packing problem and its integration into mtp, Pesquisa Operacional, 19, 111 Shaw, 2004, A constraint for bin packing, 648 Sim, 2013, Generating single and multiple cooperative heuristics for the one dimensional bin packing problem using a single node genetic programming island model, 1549 Sim, 2012, A hyper-heuristic classifier for one dimensional bin packing problems: Improving classification accuracy by attribute evolution, 348 Simchi-Levi, 1994, New worst-case results for the bin-packing problem, Naval Research Logistics, 41, 579, 10.1002/1520-6750(199406)41:4<579::AID-NAV3220410409>3.0.CO;2-G Singh, 2007, Two heuristics for the one-dimensional bin-packing problem, OR Spectrum, 29, 765, 10.1007/s00291-006-0071-2 Stadtler, 1988, A comparison of two optimization procedures for 1-and 1 1/2-dimensional cutting stock problems, Operations-Research-Spektrum, 10, 97, 10.1007/BF01720208 Stawowy, 2008, Evolutionary based heuristic for bin packing problem, Computers & Industrial Engineering, 55, 465, 10.1016/j.cie.2008.01.007 Sweeney, 1992, Cutting and packing problems: A categorized, application-orientated research bibliography, Journal of the Operational Research Society, 43, 691, 10.1057/jors.1992.101 Trick, 2003, A dynamic programming approach for consistency and propagation for knapsack constraints, Annals of Operations Research, 118, 73, 10.1023/A:1021801522545 Ülker, 2008, A grouping genetic algorithm using linear linkage encoding for bin packing, 1140 Vahrenkamp, 1996, Random search in the one-dimensional cutting stock problem, European Journal of Operational Research, 95, 191, 10.1016/0377-2217(95)00198-0 Vance, 1998, Branch-and-price algorithms for the one-dimensional cutting stock problem, Computational Optimization and Applications, 9, 211, 10.1023/A:1018346107246 Vance, 1994, Solving binary cutting stock problems by column generation and branch-and-bound, Computational Optimization and Applications, 3, 111, 10.1007/BF01300970 Vanderbeck, 1999, Computational study of a column generation algorithm for bin packing and cutting stock problems, Mathematical Programming, 86, 565, 10.1007/s101070050105 Vanderbeck, 2000, On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm, Operations Research, 48, 111, 10.1287/opre.48.1.111.12453 Vanderbeck, 2011, Branching in branch-and-price: A generic scheme, Mathematical Programming, 130, 249, 10.1007/s10107-009-0334-1 Wäscher, 1996, Heuristics for the integer one-dimensional cutting stock problem: A computational study, Operations-Research-Spektrum, 18, 131, 10.1007/BF01539705 Valério de Carvalho, 1999, Exact solution of bin-packing problems using column generation and branch-and-bound, Annals of Operations Research, 86, 629, 10.1023/A:1018952112615 Valério de Carvalho, 2002, LP models for bin packing and cutting stock problems, European Journal of Operational Research, 141, 253, 10.1016/S0377-2217(02)00124-8 Valério de Carvalho, 2005, Using extra dual cuts to accelerate column generation, INFORMS Journal on Computing, 17, 175, 10.1287/ijoc.1030.0060 Wäscher, 2007, An improved typology of cutting and packing problems, European Journal of Operational Research, 183, 1109, 10.1016/j.ejor.2005.12.047 Wolsey, 1977, Valid inequalities, covering problems and discrete dynamic programs, 527