Arcflow Formulations and Constraint Generation Frameworks for the Two Bar Charts Packing Problem

References

• 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
• Cai Q, Hang W, Mirhoseini A, Tucker G, Wang J, Wei W (2019) Reinforcement learning driven heuristic optimization. Preprint, submitted June 16, https://arxiv.org/abs/1906.06639.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).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
• Côté JF, Haouari M, Iori M (2021) Combinatorial Benders decomposition for the two-dimensional bin packing problem. INFORMS J. Comput. 33(3):963–978.Link, Google Scholar
• de Lima V, Alves C, Clautiaux F, Iori M, Valério de Carvalho J (2022) Arc flow formulations based on dynamic programming: Theoretical foundations and applications. Eur. J. Oper. Res. 296(1):3–21.Crossref, Google Scholar
• Dell’Amico M, Díaz J, Iori M (2012) The bin packing problem with precedence constraints. Oper. Res. 60(6):1491–1504.Link, Google Scholar
• Dell’Amico M, Delorme M, Iori M, Martello S (2019) Mathematical models and decomposition methods for the multiple knapsack problem. Eur. J. Oper. Res. 274(3):886–899.Crossref, Google Scholar
• Delorme M, Iori M (2020) Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS J. Comput. 32(1):101–119.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, Mendes N (2021) Solution methods for scheduling problems with sequence-dependent deterioration and maintenance events. Eur. J. Oper. Res. 295(3):823–837.Crossref, Google Scholar
• Erzin A, Melidi G, Nazarenko S, Plotnikov R (2021a) A posteriori analysis of the algorithms for two-bar charts packing problem. Olenev NN, Evtushenko YG, Malkova V, Jacimovic M, Khachay M, eds. Advances in Optimization and Applications, vol. 1514, Communications in Computer and Information Science Series (Springer, Cham, Switzerland), 201–216.Google Scholar
• Erzin A, Melidi G, Nazarenko S, Plotnikov R (2021b) Two-bar charts packing problem. Optim. Lett. 15(6):1955–1971.Crossref, Google Scholar
• Erzin A, Nazarenko S, Melidi G, Plotnikov R (2021c) A 3/2-approximation for big two-bar charts packing. J. Combin. Optim. 42(1):71–84.Crossref, Google Scholar
• Falkenauer E (1996) A hybrid grouping genetic algorithm for bin packing. J. Heuristics 2(1):5–30.Crossref, Google Scholar
• Kantorovich L (1960) Mathematical methods of organizing and planning production. Management Sci. 6(4):366–422.Link, Google Scholar
• Letelier O, Clautiaux F, Sadykov R (2022) Bin packing problem with time lags. INFORMS J. Comput. 34(4):2249–2270.Link, Google Scholar
• Lysgaard J, Letchford A, Eglese R (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Programming 100(2):423–445.Crossref, Google Scholar
• Macedo R, Alves C, Valério De Carvalho J (2010) Arc-flow model for the two-dimensional guillotine cutting stock problem. Comput. Oper. Res. 37(6):991–1001.Crossref, Google Scholar
• Martello S, Toth P (1990) Knapsack Problems: Algorithms and Computer Implementations (John Wiley & Sons, Chichester, UK).Google Scholar
• Martello S, Monaci M, Vigo D (2003) An exact approach to the strip-packing problem. INFORMS J. Comput. 15(3):310–319.Link, Google Scholar
• Martinovic J, Scheithauer G (2016) Integer linear programming models for the skiving stock problem. Eur. J. Oper. Res. 251(2):356–368.Crossref, Google Scholar
• Muritiba A, Iori M, Malaguti E, Toth P (2010) Algorithms for the bin packing problem with conflicts. INFORMS J. Comput. 22(3):401–415.Link, Google Scholar
• Nesello V, Delorme M, Iori M, Subramanian A (2018) Mathematical models and decomposition algorithms for makespan minimization in plastic rolls production. J. Oper. Res. Soc. 69(3):326–339.Crossref, Google Scholar
• Pereira J (2016) Procedures for the bin packing problem with precedence constraints. Eur. J. Oper. Res. 250(3):794–806.Crossref, Google Scholar
• Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2020) A generic exact solver for vehicle routing and related problems. Math. Programming 183(1):483–523.Crossref, Google Scholar
• Pferschy U, Staněk R (2017) Generating subtour elimination constraints for the TSP from pure integer solutions. Central Eur. J. Oper. Res. 25(1):231–260.Crossref, 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
• Shaw P (2004) A constraint for bin packing. Wallace M, ed. Principles and Practice of Constraint Programming—CP 2004, Lecture Notes in Computer Science, vol. 3258 (Springer, Berlin, Heidelberg), 648–662.Crossref, Google Scholar
• Stadtler H (1990) A one-dimensional cutting stock problem in the aluminium industry and its solution. Eur. J. Oper. Res. 44(2):209–223.Crossref, 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
• Vance P (1998) Branch-and-price algorithms for the one-dimensional cutting stock problem. Comput. Optim. Appl. 9(3):211–228.Crossref, Google Scholar
• Wei L, Lai M, Lim A, Hu Q (2020a) A branch-and-price algorithm for the two-dimensional vector packing problem. Eur. J. Oper. Res. 281(1):25–35.Crossref, Google Scholar
• Wei L, Luo Z, Baldacci R, Lim A (2020b) A new branch-and-price-and-cut algorithm for one-dimensional bin-packing problems. INFORMS J. Comput. 32(2):428–443.Link, Google Scholar
• Wolsey L (1977) Valid inequalities, covering problems and discrete dynamic programs. Hammer PL, Johnson EL, Korte BH, Nemhauser GL, eds. Studies in Integer Programming, vol. 1, Annals of Discrete Mathematics (Elsevier), 527–538.Google Scholar