Authors:
(1) Renan F. F. da Silva, Institute of Computing, University of Campinas;
(2) Yulle G. F. Borges, Institute of Computing, University of Campinas;
(3) Rafael C. S. Schouery, Institute of Computing, University of Campinas. 9 Conclusion Our approaches were quite effective, enabling us to find solutions very close to the optimal solution, even in instances with many items. These results are partly due to the excellent quality of the solutions given by Two-by-Two, which efficiently handles color constraints. Another positive factors are our neighborhoods, which are efficient in quality and time complexity. Lastly, Gilmore and Gomory Formulation has a strong relaxation for the BPP, and this property may extend to CBPP. For a strong relaxation, the values for the optimal fractional and integer solutions are very close, so the patterns used by relaxation probably belong to integer solutions of high quality. Therefore, this is an excellent method to find a good set of patterns for the initial build of GRASP. Acknowledgements This project was supported by the S˜ao Paulo Research Foundation (FAPESP) grants #2015/11937-9 and #2020/06511-0; and the Brazilian National Council For Scientific and Technological Development (CNPq) grants #144257/2019-0, #311039/2020-0 and #425340/2016 3. Declarations Conflict of interest All authors declare that they have no conflicts of interest. References [1] Alsarhan H, Chia D, Christman A, et al (2016) A two-pass algorithm for unordered colored bin packing. Proceedings of the 9th International Conference on Discrete Optimization and Operations Research and Scientific School pp 1–10 [2] Balogh J, B´ek´esi J, Dosa G, et al (2013) Black and white bin packing. In: Erlebach T, Persiano G (eds) Approximation and Online Algorithms. Springer Berlin Heidelberg, Berlin, Heidelberg, pp 131–144, https://doi.org/10.1007/978-3-642-38016-7_12 [3] Balogh J, B´ek´esi J, D´osa G, et al (2015) Offline black and white bin packing. Theoretical Computer Science 596:92–101. https://doi.org/10.1016/j.tcs.2015.06.045 [4] Belov G, Scheithauer G (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(1):85–106. https://doi.org/10.1016/j.ejor.2004.08.036 [5] B¨ohm M, Sgall J, Vesel´y P (2015) Online colored bin packing. In: Bampis E, Svensson O (eds) Approximation and Online Algorithms. Springer International Publishing, Cham, pp 35–46, https://doi.org/10.1007/978-3-319-18263-6_4 [6] B¨ohm M, D´osa G, Epstein L, et al (2018) Colored bin packing: Online algorithms and lower bounds. Algorithmica 80(1):155–184. https://doi.org/10.1007/s00453-016-0248-2 [7] Borges Y, Schouery R (2020) Modelos pseudo polinomiais para o problema do empacotamento colorido. In: Anais do V Encontro de Teoria da Computa¸c˜ao, pp 37–40, https://doi.org/ 10.5753/etc.2020.11084, (In Portuguese) [8] Borges YGF, Schouery RCS, Miyazawa FK (2023) Mathematical models and exact algorithms for the colored bin packing problem. 2305.15291 [9] Brand˜ao F, Pedroso JP (2016) Bin packing and related problems: General arc-flow formulation with graph compression. Computers & Operations Research 69:56–67. https://doi.org/10. 1016/j.cor.2015.11.009 [10] Buljubaˇsi´c M, Vasquez M (2016) Consistent neighborhood search for one-dimensional bin packing and two-dimensional vector packing. Computers & Operations Research 76:12–21. https://doi.org/10.1016/j.cor.2016.06.009 [11] Carvalho JMVd (1999) Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research 86(0):629–659. https://doi.org/10. 1023/A:1018952112615 [12] Castelli M, Vanneschi L (2014) A hybrid harmony search algorithm with variable neighbourhood search for the bin-packing problem. 2014 Sixth World Congress on Nature and Biologically Inspired Computing (NaBIC 2014) pp 1–6. https://doi.org/10.1109/NaBIC.2014. 6921849 [13] Chen J, Han X, Bein W, et al (2015) Black and white bin packing revisited. In: Lu Z, Kim D, Wu W, et al (eds) Combinatorial Optimization and Applications. Springer International Publishing, Cham, pp 45–59, https://doi.org/10.1007/978-3-319-26626-8_4 [14] Delorme M, Iori M (2020) Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS Journal on Computing 32(1):101–119. https://doi.org/ 10.1287/ijoc.2018.0880 [15] Delorme M, Iori M, Martello S (2018) Bpplib: a library for bin packing and cutting stock problems. Optimization Letters 12(2):235–250. https://doi.org/10.1007/s11590-017-1192-z [16] Demˇsar J (2006) Statistical comparisons of classifiers over multiple data sets. The Journal of Machine learning research 7:1–30 [17] D´osa G, Epstein L (2014) Colorful bin packing. In: Ravi R, Gørtz IL (eds) Algorithm Theory – SWAT 2014. Springer International Publishing, Cham, pp 170–181, https://doi.org/10. 1007/978-3-319-08404-6_15 [18] Feo TA, Resende MG (1989) A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters 8(2):67–71. https://doi.org/https://doi.org/ 10.1016/0167-6377(89)90002-3 [19] Fleszar K, Hindi KS (2002) New heuristics for one-dimensional bin-packing. Computers & Operations Research 29(7):821–839. https://doi.org/10.1016/S0305-0548(00)00082-4 [20] Friedman M (1937) The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the American Statistical Association 32(200):675–701. https: //doi.org/10.1080/01621459.1937.10503522 [21] Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Operations Research 9(6):849–859. https://doi.org/10.1287/opre.29.6.1092 [22] Gonz´alez-San-Mart´ın J, Cruz-Reyes L, G´omez-Santill´an C, et al (2023) Comparative Study of Heuristics for the One-Dimensional Bin Packing Problem, Springer Nature Switzerland, Cham, pp 293–305. https://doi.org/10.1007/978-3-031-28999-6_19 [23] Gupta JND, Ho JC (1999) A new heuristic algorithm for the one-dimensional binpacking problem. Production Planning & Control 10(6):598–603. https://doi.org/10.1080/ 095372899232894 [24] Iman RL, Davenport JM (1980) Approximations of the critical region of the fbietkan statistic. Communications in Statistics - Theory and Methods 9(6):571–595. https://doi.org/10. 1080/03610928008827904 [25] Karp RM (1972) Reducibility among Combinatorial Problems, Springer US, Boston, MA, pp 85–103. https://doi.org/10.1007/978-1-4684-2001-2_9 [26] de Lima VL, Iori M, Miyazawa FK (2022) Exact solution of network flow models with strong relaxations. Mathematical Programming pp 1–34. https://doi.org/10.1007/ s10107-022-01785-9 [27] Loh KH, Golden B, Wasil E (2008) Solving the one-dimensional bin packing problem with a weight annealing heuristic. Computers & Operations Research 35(7):2283–2291. https:// doi.org/10.1016/j.cor.2006.10.021 [28] Mladenovi´c N, Hansen P (1997) Variable neighborhood search. Computers & Operations Research 24(11):1097–1100. https://doi.org/10.1016/S0305-0548(97)00031-2 [29] Nemenyi PB (1963) Distribution-free multiple comparisons. PhD thesis, Princeton University [30] Pessoa A, Sadykov R, Uchoa E, et al (2020) A generic exact solver for vehicle routing and related problems. Mathematical Programming 183(1):483–523. https://doi.org/10.1007/ s10107-020-01523-z [31] Vance PH (1998) Branch-and-price algorithms for the one-dimensional cutting stock problem. Computational Optimization and Applications 9(3):211–228. https://doi.org/10.1023/A: 1018346107246 [32] Wei L, Luo Z, Baldacci R, et al (2020) A new branch-and-price-and-cut algorithm for onedimensional bin-packing problems. INFORMS Journal on Computing 32(2):428–443. https://doi.org/10.1287/ijoc.2018.0867 This paper is available on arxiv under CC 4.0 license. Authors: (1) Renan F. F. da Silva, Institute of Computing, University of Campinas; (2) Yulle G. F. Borges, Institute of Computing, University of Campinas; (3) Rafael C. S. Schouery, Institute of Computing, University of Campinas. Authors: (1) Renan F. F. da Silva, Institute of Computing, University of Campinas; (2) Yulle G. F. Borges, Institute of Computing, University of Campinas; (3) Rafael C. S. Schouery, Institute of Computing, University of Campinas. 9 Conclusion Our approaches were quite effective, enabling us to find solutions very close to the optimal solution, even in instances with many items. These results are partly due to the excellent quality of the solutions given by Two-by-Two, which efficiently handles color constraints. Another positive factors are our neighborhoods, which are efficient in quality and time complexity. Lastly, Gilmore and Gomory Formulation has a strong relaxation for the BPP, and this property may extend to CBPP. For a strong relaxation, the values for the optimal fractional and integer solutions are very close, so the patterns used by relaxation probably belong to integer solutions of high quality. Therefore, this is an excellent method to find a good set of patterns for the initial build of GRASP. Acknowledgements This project was supported by the S˜ao Paulo Research Foundation (FAPESP) grants #2015/11937-9 and #2020/06511-0; and the Brazilian National Council For Scientific and Technological Development (CNPq) grants #144257/2019-0, #311039/2020-0 and #425340/2016 3. Acknowledgements Declarations Conflict of interest All authors declare that they have no conflicts of interest. Conflict of interest References [1] Alsarhan H, Chia D, Christman A, et al (2016) A two-pass algorithm for unordered colored bin packing. Proceedings of the 9th International Conference on Discrete Optimization and Operations Research and Scientific School pp 1–10 [2] Balogh J, B´ek´esi J, Dosa G, et al (2013) Black and white bin packing. In: Erlebach T, Persiano G (eds) Approximation and Online Algorithms. Springer Berlin Heidelberg, Berlin, Heidelberg, pp 131–144, https://doi.org/10.1007/978-3-642-38016-7_12 [3] Balogh J, B´ek´esi J, D´osa G, et al (2015) Offline black and white bin packing. Theoretical Computer Science 596:92–101. https://doi.org/10.1016/j.tcs.2015.06.045 [4] Belov G, Scheithauer G (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(1):85–106. https://doi.org/10.1016/j.ejor.2004.08.036 [5] B¨ohm M, Sgall J, Vesel´y P (2015) Online colored bin packing. In: Bampis E, Svensson O (eds) Approximation and Online Algorithms. Springer International Publishing, Cham, pp 35–46, https://doi.org/10.1007/978-3-319-18263-6_4 [6] B¨ohm M, D´osa G, Epstein L, et al (2018) Colored bin packing: Online algorithms and lower bounds. Algorithmica 80(1):155–184. https://doi.org/10.1007/s00453-016-0248-2 [7] Borges Y, Schouery R (2020) Modelos pseudo polinomiais para o problema do empacotamento colorido. In: Anais do V Encontro de Teoria da Computa¸c˜ao, pp 37–40, https://doi.org/ 10.5753/etc.2020.11084, (In Portuguese) [8] Borges YGF, Schouery RCS, Miyazawa FK (2023) Mathematical models and exact algorithms for the colored bin packing problem. 2305.15291 [9] Brand˜ao F, Pedroso JP (2016) Bin packing and related problems: General arc-flow formulation with graph compression. Computers & Operations Research 69:56–67. https://doi.org/10. 1016/j.cor.2015.11.009 [10] Buljubaˇsi´c M, Vasquez M (2016) Consistent neighborhood search for one-dimensional bin packing and two-dimensional vector packing. Computers & Operations Research 76:12–21. https://doi.org/10.1016/j.cor.2016.06.009 [11] Carvalho JMVd (1999) Exact solution of bin-packing problems using column generation and branch-and-bound. Annals of Operations Research 86(0):629–659. https://doi.org/10. 1023/A:1018952112615 [12] Castelli M, Vanneschi L (2014) A hybrid harmony search algorithm with variable neighbourhood search for the bin-packing problem. 2014 Sixth World Congress on Nature and Biologically Inspired Computing (NaBIC 2014) pp 1–6. https://doi.org/10.1109/NaBIC.2014. 6921849 [13] Chen J, Han X, Bein W, et al (2015) Black and white bin packing revisited. In: Lu Z, Kim D, Wu W, et al (eds) Combinatorial Optimization and Applications. Springer International Publishing, Cham, pp 45–59, https://doi.org/10.1007/978-3-319-26626-8_4 [14] Delorme M, Iori M (2020) Enhanced pseudo-polynomial formulations for bin packing and cutting stock problems. INFORMS Journal on Computing 32(1):101–119. https://doi.org/ 10.1287/ijoc.2018.0880 [15] Delorme M, Iori M, Martello S (2018) Bpplib: a library for bin packing and cutting stock problems. Optimization Letters 12(2):235–250. https://doi.org/10.1007/s11590-017-1192-z [16] Demˇsar J (2006) Statistical comparisons of classifiers over multiple data sets. The Journal of Machine learning research 7:1–30 [17] D´osa G, Epstein L (2014) Colorful bin packing. In: Ravi R, Gørtz IL (eds) Algorithm Theory – SWAT 2014. Springer International Publishing, Cham, pp 170–181, https://doi.org/10. 1007/978-3-319-08404-6_15 [18] Feo TA, Resende MG (1989) A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters 8(2):67–71. https://doi.org/https://doi.org/ 10.1016/0167-6377(89)90002-3 [19] Fleszar K, Hindi KS (2002) New heuristics for one-dimensional bin-packing. Computers & Operations Research 29(7):821–839. https://doi.org/10.1016/S0305-0548(00)00082-4 [20] Friedman M (1937) The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the American Statistical Association 32(200):675–701. https: //doi.org/10.1080/01621459.1937.10503522 [21] Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Operations Research 9(6):849–859. https://doi.org/10.1287/opre.29.6.1092 [22] Gonz´alez-San-Mart´ın J, Cruz-Reyes L, G´omez-Santill´an C, et al (2023) Comparative Study of Heuristics for the One-Dimensional Bin Packing Problem, Springer Nature Switzerland, Cham, pp 293–305. https://doi.org/10.1007/978-3-031-28999-6_19 [23] Gupta JND, Ho JC (1999) A new heuristic algorithm for the one-dimensional binpacking problem. Production Planning & Control 10(6):598–603. https://doi.org/10.1080/ 095372899232894 [24] Iman RL, Davenport JM (1980) Approximations of the critical region of the fbietkan statistic. Communications in Statistics - Theory and Methods 9(6):571–595. https://doi.org/10. 1080/03610928008827904 [25] Karp RM (1972) Reducibility among Combinatorial Problems, Springer US, Boston, MA, pp 85–103. https://doi.org/10.1007/978-1-4684-2001-2_9 [26] de Lima VL, Iori M, Miyazawa FK (2022) Exact solution of network flow models with strong relaxations. Mathematical Programming pp 1–34. https://doi.org/10.1007/ s10107-022-01785-9 [27] Loh KH, Golden B, Wasil E (2008) Solving the one-dimensional bin packing problem with a weight annealing heuristic. Computers & Operations Research 35(7):2283–2291. https:// doi.org/10.1016/j.cor.2006.10.021 [28] Mladenovi´c N, Hansen P (1997) Variable neighborhood search. Computers & Operations Research 24(11):1097–1100. https://doi.org/10.1016/S0305-0548(97)00031-2 [29] Nemenyi PB (1963) Distribution-free multiple comparisons. PhD thesis, Princeton University [30] Pessoa A, Sadykov R, Uchoa E, et al (2020) A generic exact solver for vehicle routing and related problems. Mathematical Programming 183(1):483–523. https://doi.org/10.1007/ s10107-020-01523-z [31] Vance PH (1998) Branch-and-price algorithms for the one-dimensional cutting stock problem. Computational Optimization and Applications 9(3):211–228. https://doi.org/10.1023/A: 1018346107246 [32] Wei L, Luo Z, Baldacci R, et al (2020) A new branch-and-price-and-cut algorithm for onedimensional bin-packing problems. INFORMS Journal on Computing 32(2):428–443. https://doi.org/10.1287/ijoc.2018.0867 This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Fast Neighborhood Search Heuristics for the Colorful Bin Packing Problem: Conclusion and References

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

5 Smart Heuristic Methods for Solving Bin Packing Problems