Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems

References

• Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, Upper Saddle River, NJ).Google Scholar
• Alves C, Valério de Carvalho J (2008) A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem. Comput. Oper. Res. 35(4):1315–1328.Crossref, Google Scholar
• Alves C, Clautiaux F, Valério de Carvalho J, Rietz J (2016) Dual-Feasible Functions for Integer Programming and Combinatorial Optimization, EURO Advanced Tutorials on Operational Research (Springer International Publishing, Cham, Switzerland).Google Scholar
• Arbib C, Marinelli F, Rossi F, Di Iorio F (2002) Cutting and reuse: An application from automobile component manufacturing. Oper. Res. 50(6):923–934.Link, Google Scholar
• Belov G, Scheithauer G (2002) A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths. Eur. J. Oper. Res. 141(2):274–294.Crossref, Google Scholar
• Belov G, Scheithauer G (2006) A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. Eur. J. Oper. Res. 171(1):85–106.Crossref, Google Scholar
• Boschetti M, Montaletti L (2010) An exact algorithm for the two-dimensional strip-packing problem. Oper. Res. 58(6):1774–1791.Link, Google Scholar
• Brandão F, Pedroso J (2016) Bin packing and related problems: General arc-flow formulation with graph compression. Comput. Oper. Res. 69:56–67.Crossref, Google Scholar
• Cambazard H, O’Sullivan B (2010) Propagating the bin packing constraint using linear programming. Cohen D, ed. Principles and Practice of Constraint Programming—CP 2010, Lecture Notes in Computer Science, vol. 6308 (Springer-Verlag, Berlin), 129–136.Crossref, Google Scholar
• Caprara A, Dell’Amico M, Díaz J, Iori M, Rizzi R (2015) Friendly bin packing instances without integer round-up property. Math. Programming 150(1):5–17.Crossref, Google Scholar
• Casazza M, Ceselli A (2016) Exactly solving packing problems with fragmentation. Comput. Oper. Res. 75:202–213.Crossref, Google Scholar
• Ceselli A, Righini G (2008) An optimization algorithm for the ordered open-end bin-packing problem. Oper. Res. 56(2):425–436.Link, Google Scholar
• Clautiaux F, Hanafi S, Macedo R, Voge ME, Alves C (2017) Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints. Eur. J. Oper. Res. 258(2):467–477.Crossref, Google Scholar
• Coffman E, Csirik J, Galambos G, Martello S, Vigo D (2013) Bin packing approximation algorithms: Survey and classification. Pardalos P, Du DZ, Graham R, eds. Handbook of Combinatorial Optimization (Springer, New York), 455–531.Crossref, Google Scholar
• Correia I, Gouveia L, Saldanha-da-Gama F (2008) Solving the variable size bin packing problem with discretized formulations. Comput. Oper. Res. 35(6):2103–2113.Crossref, Google Scholar
• Côté JF, Iori M (2018) The meet-in-the-middle principle for cutting and packing problems. INFORMS J. Comput. 30(4):646–661.Link, Google Scholar
• Côté JF, Dell’Amico M, Iori M (2014) Combinatorial Benders’ cuts for the strip packing problem. Oper. Res. 62(3):643–661.Link, Google Scholar
• Crainic T, Perboli G, Rei W, Tadei R (2011) Efficient lower bounds and heuristics for the variable cost and size bin packing problem. Comput. Oper. Res. 38(11):1474–1482.Crossref, Google Scholar
• Dell’Amico M, Díaz-Díaz J, Iori M (2012) The bin packing problem with precedence constraints. Oper. Res. 60(6):1491–1504.Link, Google Scholar
• Delorme M, Iori M, Martello S (2016) Bin packing and cutting stock problems: Mathematical models and exact algorithms. Eur. J. Oper. Res. 255(1):1–20.Crossref, Google Scholar
• Delorme M, Iori M, Martello S (2017) Logic based Benders’ decomposition for orthogonal stock cutting problems. Comput. Oper. Res. 78:290–298.Crossref, Google Scholar
• Delorme M, Iori M, Martello S (2018) Bpplib: A library for bin packing and cutting stock problems. Optim. Lett. 12(2):235–250.Crossref, Google Scholar
• Dyckhoff H (1981) A new linear programming approach to the cutting stock problem. Oper. Res. 29(6):1092–1104.Link, Google Scholar
• Furini F, Malaguti E, Thomopulos D (2016) Modeling two-dimensional guillotine cutting problems via integer programming. INFORMS J. Comput. 28(4):736–751.Link, Google Scholar
• Gilmore P, Gomory R (1961) A linear programming approach to the cutting-stock problem. Oper. Res. 9(6):849–859.Link, Google Scholar
• Gschwind T, Irnich S (2016) Dual inequalities for stabilized column generation revisited. INFORMS J. Comput. 28(1):175–194.Link, Google Scholar
• Hemmelmayr V, Schmid V, Blum C (2012) Variable neighbourhood search for the variable sized bin packing problem. Comput. Oper. Res. 39(5):1097–1108.Crossref, Google Scholar
• Kartak V, Ripatti A, Scheithauer G, Kurz S (2015) Minimal proper non-IRUP instances of the one-dimensional cutting stock problem. Discrete Appl. Math. 187:120–129.Crossref, Google Scholar
• Macedo R, Alves C, Valério de Carvalho J, Clautiaux F, Hanafi S (2011) Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model. Eur. J. Oper. Res. 214(3):536–545.Crossref, Google Scholar
• Martello S, Pisinger D, Toth P (1999) Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Sci. 45(3):414–424.Link, Google Scholar
• Martinovic J, Scheithauer G, de Carvalho JV (2018) A comparative study of the arcflow model and the one-cut model for one-dimensional cutting stock problems. Eur. J. Oper. Res. 266(2):458–471.Crossref, Google Scholar
• Nitsche C, Scheithauer G, Terno J (1999) Tighter relaxations for the cutting stock problem. Eur. J. Oper. Res. 112(3):654–663.Crossref, Google Scholar
• Pessoa A, Uchoa E, Poggi de Aragão M, Rodrigues R (2010) Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems. Math. Programming Comput. 2(3–4):259–290.Crossref, Google Scholar
• Rao M (1976) On the cutting stock problem. J. Comput. Soc. India 7:35–39.Google Scholar
• Sadykov R, Vanderbeck F (2013) Bin packing with conflicts: A generic branch-and-price algorithm. INFORMS J. Comput. 25(2):244–255.Link, Google Scholar
• Sadykov R, Vanderbeck F, Pessoa A, Tahiri I, Uchoa E (2019) Primal heuristics for branch-and-price: The assets of diving methods. INFORMS J. Comput. 31(2):251–267.Link, Google Scholar
• Shapiro J (1968) Dynamic programming algorithms for the integer programming problem. I. The integer programming problem viewed as a knapsack type problem. Oper. Res. 16(1):103–121.Link, Google Scholar
• Valério de Carvalho J (1999) Exact solution of bin-packing problems using column generation and branch-and-bound. Ann. Oper. Res. 86:629–659.Crossref, Google Scholar
• Valério de Carvalho J (2002) LP models for bin packing and cutting stock problems. Eur. J. Oper. Res. 141(2):253–273.Crossref, Google Scholar
• Valério de Carvalho J (2005) Using extra dual cuts to accelerate column generation. INFORMS J. Comput. 17(2):175–182.Link, Google Scholar
• Vanderbeck F (1999) Computational study of a column generation algorithm for bin packing and cutting stock problems. Math. Programming 86(3):565–594.Crossref, Google Scholar
• Vanderbeck F, Wolsey L (2010) Reformulation and decomposition of integer programs. Jünger M, Liebling T, Naddef D, Nemhauser G, Pulleyblank W, Reinelt G, Rinaldi G, Wolsey L, eds. 50 Years of Integer Programming 1958–2008: From the Early Years to the State-of-the-Art (Springer, Berlin), 431–502.Crossref, Google Scholar
• Wolsey L (1977) Valid inequalities, covering problems and discrete dynamic programs. Ann. Discrete Math. 1:527–538.Crossref, Google Scholar