Pseudo-Polynomial Formulations for the Bin Packing Problem with Minimum Color Fragmentation

References

• Barkel M, Delorme M (2023) Arcflow formulations and constraint generation frameworks for the two bar charts packing problem. INFORMS J. Comput. 35(2):475–494.Link, Google Scholar
• Barkel M, Delorme M, Malaguti E, Monaci M (2025a) Bounds and heuristic algorithms for the bin packing problem with minimum color fragmentation. Eur. J. Oper. Res. 320(1):57–68.Crossref, Google Scholar
• Barkel M, Delorme M, Malaguti E, Monaci M (2025b) Pseudo-polynomial formulations for the bin packing problem with minimum color fragmentation. https://doi.org/10.1287/ijoc.2024.0972.cd, https://github.com/INFORMSJoC/2024.0972.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
• Bergman D, Cardonha C, Mehrani S (2019) Binary decision diagrams for bin packing with minimum color fragmentation. Rousseau L-M, Stergiou K, eds. Integration of Constraint Programming, Artificial Intelligence, and Operations Research (Springer International Publishing, Cham, Switzerland), 57–66.Crossref, 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. Principles and Practice of Constraint Programming–CP 2010, Lecture Notes in Computer Science, vol. 6308 (Springer-Verlag, Berlin), 129–136.Crossref, Google Scholar
• Casazza M, Ceselli A (2016) Exactly solving packing problems with fragmentation. Comput. Oper. Res. 75:202–213.Crossref, Google Scholar
• Coffman Jr E, Garey M, Johnson D (1987) Bin packing with divisible item sizes. J. Complexity 3(4):406–428.Crossref, Google Scholar
• Côté J, Iori M (2018) The meet-in-the-middle principle for cutting and packing problems. INFORMS J. Comput. 30(4):646–661.Link, Google Scholar
• de Lima V, Iori M, Miyazawa F (2023) Exact solution of network flow models with strong relaxations. Math. Programming 197(2):813–846.Crossref, 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
• 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
• Erzin A, Melidi G, Nazarenko S, Plotnikov R (2021) Two-bar charts packing problem. Optim. Lett. 15(6):1955–1971.Crossref, Google Scholar
• Falkenauer E (1996) A hybrid grouping genetic algorithm for bin packing. J. Heuristics 2(1):5–30.Crossref, Google Scholar
• Fernandes-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
• Kantorovich L (1960) Mathematical methods of organizing and planning production. Management Sci. 6(4):366–422.Link, Google Scholar
• Martello S, Toth P (1990a) Knapsack Problems: Algorithms and Computer Implementations (John Wiley & Sons, Chichester, UK).Google Scholar
• Martello S, Toth P (1990b) Lower bounds and reduction procedures for the bin packing problem. Discrete Appl. Math. 28(1):59–70.Crossref, Google Scholar
• Mehrani S, Cardonha C, Bergman D (2022) Models and algorithms for the bin-packing problem with minimum color fragmentation. INFORMS J. Comput. 34(2):1070–1085.Link, 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
• Romera-Paredes B, Barekatain M, Novikov A, Balog M, Kumar M, Dupont E, Ruiz F, et al. (2024) Mathematical discoveries from program search with large language model. Nature 625(7995):468–475.Crossref, 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
• Trick M (2003) A dynamic programming approach for consistency and propagation for knapsack constraints. Ann. Oper. Res. 118(1):73–84.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
• Wei L, Luo Z, Baldacci R, Lim A (2020) 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 LA (1977) Valid inequalities, covering problems and discrete dynamic programs. Hammer, P, Johnson E, Korte B, Nemhauser G, eds. Studies in Integer Programming, Annals of Discrete Mathematics, vol. 1 (Elsevier, Amsterdam), 527–538.Crossref, Google Scholar