Nothing Special   »   [go: up one dir, main page]
Document Open Access Logo

CP for Bin Packing with Multi-Core and GPUs

Authors Fabio Tardivo , Laurent Michel , Enrico Pontelli

PDF
Thumbnail PDF

File

LIPIcs.CP.2024.28.pdf
  • Filesize: 1.05 MB
  • 19 pages

Document Identifiers

Author Details

Fabio Tardivo
  • Department of Computer Science, New Mexico State University, Las Cruces, NM, USA
Laurent Michel
  • Synchrony Chair in Cybersecurity, School of Computing, University of Connecticut, Storrs, CT, USA
Enrico Pontelli
  • Department of Computer Science, New Mexico State University, Las Cruces, NM, USA

Funding

Enrico Pontelli and Fabio Tardivo: Supported by NSF grants 2151254, 1914635 and by a contract from Wallaroo Inc.
  • Michel, Laurent: Partially supported by Synchrony.

Acknowledgements

We would like to thank François Clautiaux, Maxence Delorme, Jürgen Rietz for their feedbacks, and Hadrien Cambazard for providing the Arc-Flow implementation.

Cite As Get BibTex

Fabio Tardivo, Laurent Michel, and Enrico Pontelli. CP for Bin Packing with Multi-Core and GPUs. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 28:1-28:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024) https://doi.org/10.4230/LIPIcs.CP.2024.28

Abstract

The BinPacking constraint models the requirements of many logistics, resource allocation, and production scheduling applications. This paper explores new avenues based on the impressive computational power of modern GPUs to propagate the BinPacking constraint. This work showcases how the perspective of massive parallelization can lead to novel approaches, such as the use of a portfolio of lower bounds, to enhance the pruning of the BinPacking constraints. It delivers insights into the design choices and challenges presented by GPU platform for constraint propagation.
The paper evaluates a GPU-accelerated propagator against both sequential and parallel CPU versions, as well as state-of-the-art approaches. Comparisons across various benchmarks from the literature show strong performances with respect to both CPU versions and the standard pruning approach. When compared to techniques based on Linear Programming, our approach proves valuable for large instances or when spending extensive time to obtain the best possible bound is not convenient.

Subject Classification

ACM Subject Classification
  • Theory of computation → Constraint and logic programming
  • Theory of computation → Massively parallel algorithms
Keywords
  • Constraint Propagation
  • Bin Packing
  • Parallelism
  • GPU
  • Lower Bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Cláudio Alves, Francois Clautiaux, José Valério de Carvalho, and Jürgen Rietz. Dual-feasible functions for integer programming and combinatorial optimization. EURO Advanced Tutorials on Operational Research. Springer International Publishing, Basel, Switzerland, 2016. Google Scholar
  2. Cláudio Alves, José M. Valério de Carvalho, François Clautiaux, and Jürgen Rietz. Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem. Eur. J. Oper. Res., 233(1):43-63, 2014. URL: https://doi.org/10.1016/J.EJOR.2013.08.011.
  3. Hadrien Cambazard and Barry O'Sullivan. Propagating the bin packing constraint using linear programming. In David Cohen, editor, Principles and Practice of Constraint Programming - CP 2010 - 16th International Conference, CP 2010, St. Andrews, Scotland, UK, September 6-10, 2010. Proceedings, volume 6308 of Lecture Notes in Computer Science, pages 129-136. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-15396-9_13.
  4. Alberto Caprara, Mauro Dell'Amico, José Carlos Díaz Díaz, Manuel Iori, and Romeo Rizzi. Friendly bin packing instances without integer round-up property. Math. Program., 150(1):5-17, 2015. URL: https://doi.org/10.1007/S10107-014-0791-Z.
  5. Ignacio Castiñeiras, Milan De Cauwer, and Barry O'Sullivan. Weibull-based benchmarks for bin packing. In Michela Milano, editor, Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Québec City, QC, Canada, October 8-12, 2012. Proceedings, volume 7514 of Lecture Notes in Computer Science, pages 207-222. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-33558-7_17.
  6. François Clautiaux, Cláudio Alves, and José M. Valério de Carvalho. A survey of dual-feasible and superadditive functions. Ann. Oper. Res., 179(1):317-342, 2010. URL: https://doi.org/10.1007/S10479-008-0453-8.
  7. Michele Collevati, Agostino Dovier, and Andrea Formisano. GPU parallelism for SAT solving heuristics. In Roberta Calegari, Giovanni Ciatto, and Andrea Omicini, editors, Proceedings of the CILC'22, volume 3204 of CEUR Workshop Proceedings, pages 17-31. CEUR-WS.org, 2022. Google Scholar
  8. Alessandro Dal Palù, Agostino Dovier, Andrea Formisano, and Enrico Pontelli. CUD@SAT: SAT solving on GPUs. J. Exp. Theor. Artif. Intell., 27(3):293-316, 2015. URL: https://doi.org/10.1080/0952813X.2014.954274.
  9. José M. Valério de Carvalho. Exact solution of bin-packing problems using column generation and branch-and-bound. Ann. Oper. Res., 86:629-659, 1999. URL: https://doi.org/10.1023/A%3A1018952112615.
  10. Maxence Delorme, Manuel Iori, and Silvano Martello. Bin packing and cutting stock problems: Mathematical models and exact algorithms. European Journal of Operational Research, 255(1):1-20, November 2016. URL: https://doi.org/10.1016/j.ejor.2016.04.030.
  11. Guillaume Derval, Jean-Charles Régin, and Pierre Schaus. Improved filtering for the bin-packing with cardinality constraint. Constraints An Int. J., 23(3):251-271, 2018. URL: https://doi.org/10.1007/S10601-017-9278-X.
  12. Agostino Dovier, Andrea Formisano, and Enrico Pontelli. Parallel answer set programming. In Youssef Hamadi and Lakhdar Sais, editors, Handbook of Parallel Constraint Reasoning, pages 237-282. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-63516-3_7.
  13. Agostino Dovier, Andrea Formisano, and Flavio Vella. GPU-Based Parallelism for ASP-Solving. In Petra Hofstedt, Salvador Abreu, Ulrich John, Herbert Kuchen, and Dietmar Seipel, editors, Declarative Programming and Knowledge Management, volume 12057 of Lecture Notes in Computer Science, pages 3-23. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-46714-2_1.
  14. Julien Dupuis, Pierre Schaus, and Yves Deville. Consistency check for the bin packing constraint revisited. In Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pages 117-122. Springer Berlin Heidelberg, 2010. URL: https://doi.org/10.1007/978-3-642-13520-0_15.
  15. Emanuel Falkenauer. A hybrid grouping genetic algorithm for bin packing. J. Heuristics, 2(1):5-30, 1996. URL: https://doi.org/10.1007/BF00226291.
  16. Sándor P. Fekete and Jörg Schepers. New classes of fast lower bounds for bin packing problems. Math. Program., 91(1):11-31, 2001. URL: https://doi.org/10.1007/S101070100243.
  17. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  18. Rebecca Gentzel, Laurent Michel, and W.-J. van Hoeve. HADDOCK: A language and architecture for decision diagram compilation. In Lecture Notes in Computer Science, pages 531-547. Springer International Publishing, Cham, 2020. URL: https://doi.org/10.1007/978-3-030-58475-7_31.
  19. Michel X. Goemans and Thomas Rothvoss. Polynomiality for bin packing with a constant number of item types. J. ACM, 67(6):38:1-38:21, 2020. URL: https://doi.org/10.1145/3421750.
  20. Wen-Mei W Hwu, David B Kirk, and Izzat El Hajj. Programming Massively Parallel Processors: A Hands-on Approach. Morgan Kaufmann, 2022. URL: https://shop.elsevier.com/books/programming-massively-parallel-processors/hwu/978-0-323-91231-0.
  21. Klaus Jansen, Stefan Kratsch, Dániel Marx, and Ildikó Schlotter. Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci., 79(1):39-49, 2013. URL: https://doi.org/10.1016/j.jcss.2012.04.004.
  22. Richard E. Korf. A new algorithm for optimal bin packing. In Rina Dechter and Michael J. Kearns andRichard S. Sutton, editors, Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, July 28 - August 1, 2002, Edmonton, Alberta, Canada, pages 731-736. AAAI Press / The MIT Press, 2002. URL: http://www.aaai.org/Library/AAAI/2002/aaai02-110.php.
  23. Alan K. Mackworth. Consistency in networks of relations. Artif. Intell., 8(1):99-118, 1977. URL: https://doi.org/10.1016/0004-3702(77)90007-8.
  24. Silvano Martello and Paolo Toth. Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Inc., 1990. Google Scholar
  25. Silvano Martello and Paolo Toth. Lower bounds and reduction procedures for the bin packing problem. Discret. Appl. Math., 28:59-70, 1990. URL: https://doi.org/10.1016/0166-218X(90)90094-S.
  26. L. Michel, P. Schaus, and P. Van Hentenryck. MiniCP: a lightweight solver for constraint programming. Mathematical Programming Computation, pages 133-184, 2021. URL: https://doi.org/10.1007/s12532-020-00190-7.
  27. Nicholas Nethercote, Peter J. Stuckey, Ralph Becket, Sebastian Brand, Gregory J. Duck, and Guido Tack. Minizinc: Towards a standard CP modelling language. In Christian Bessiere, editor, Principles and Practice of Constraint Programming - CP 2007, 13th International Conference, CP 2007, Providence, RI, USA, September 23-27, 2007, Proceedings, volume 4741 of Lecture Notes in Computer Science, pages 529-543. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-74970-7_38.
  28. Nvidia Team. CUDA. URL: https://developer.nvidia.com/cuda-toolkit.
  29. OpenMP Team. OpenMP. URL: https://www.openmp.org/.
  30. François Pelsser, Pierre Schaus, and Jean-Charles Régin. Revisiting the cardinality reasoning for binpacking constraint. In Christian Schulte, editor, Principles and Practice of Constraint Programming - 19th International Conference, CP 2013, Uppsala, Sweden, September 16-20, 2013. Proceedings, volume 8124 of Lecture Notes in Computer Science, pages 578-586. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-40627-0_43.
  31. Jürgen Rietz, Cláudio Alves, and José M. Valério de Carvalho. Theoretical investigations on maximal dual feasible functions. Oper. Res. Lett., 38(3):174-178, 2010. URL: https://doi.org/10.1016/J.ORL.2010.01.002.
  32. Jürgen Rietz, Cláudio Alves, and José M. Valério de Carvalho. Worst-case analysis of maximal dual feasible functions. Optim. Lett., 6(8):1687-1705, 2012. URL: https://doi.org/10.1007/S11590-011-0359-2.
  33. Khadija Hadj Salem and Yann Kieffer. An experimental study on symmetry breaking constraints impact for the one dimensional bin-packing problem. In Maria Ganzha, Leszek A. Maciaszek, and Marcin Paprzycki, editors, Proceedings of the 2020 Federated Conference on Computer Science and Information Systems, FedCSIS 2020, Sofia, Bulgaria, September 6-9, 2020, volume 21 of Annals of Computer Science and Information Systems, pages 317-326, 2020. URL: https://doi.org/10.15439/2020F19.
  34. Pierre Schaus. Solving Balancing and Bin-Packing problems with Constraint Programming. PhD thesis, University of Louvain, 2009. URL: http://cp2013.a4cp.org/sites/default/files/pierre_schaus_-_mr.pdf.
  35. Pierre Schaus, Jean-Charles Régin, Rowan Van Schaeren, Wout Dullaert, and Birger Raa. Cardinality reasoning for bin-packing constraint: Application to a tank allocation problem. In Michela Milano, editor, Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Québec City, QC, Canada, October 8-12, 2012. Proceedings, volume 7514 of Lecture Notes in Computer Science, pages 815-822. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-33558-7_58.
  36. Guntram Scheithauer. Introduction to Cutting and Packing Optimization. Springer International Publishing, 2018. URL: https://doi.org/10.1007/978-3-319-64403-5.
  37. Armin Scholl, Robert Klein, and Christian Jürgens. Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Comput. Oper. Res., 24(7):627-645, 1997. URL: https://doi.org/10.1016/S0305-0548(96)00082-2.
  38. Paul Shaw. A constraint for bin packing. In Principles and Practice of Constraint Programming endash CP 2004, pages 648-662. Springer Berlin Heidelberg, 2004. URL: https://doi.org/10.1007/978-3-540-30201-8_47.
  39. Fabio Tardivo. Fzn-MiniCPP. URL: https://bitbucket.org/constraint-programming/fzn-minicpp.
  40. Fabio Tardivo. MiniCPP-Benchmarks. URL: https://bitbucket.org/constraint-programming/minicpp-benchmarks.
  41. Fabio Tardivo, Agostino Dovier, Andrea Formisano, Laurent Michel, and Enrico Pontelli. Constraint propagation on GPU: A case study for the AllDifferent constraint. Journal of Logic and Computation, page exad033, June 2023. URL: https://doi.org/10.1093/logcom/exad033.
  42. Fabio Tardivo, Agostino Dovier, Andrea Formisano, Laurent Michel, and Enrico Pontelli. Constraint propagation on GPU: A case study for the cumulative constraint. In André A. Ciré, editor, Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 20th International Conference, CPAIOR 2023, Nice, France, May 29 - June 1, 2023, Proceedings, volume 13884 of Lecture Notes in Computer Science, pages 336-353. Springer, 2023. URL: https://doi.org/10.1007/978-3-031-33271-5_22.
  43. Michael A. Trick. A dynamic programming approach for consistency and propagation for knapsack constraints. Ann. Oper. Res., 118(1-4):73-84, 2003. URL: https://doi.org/10.1023/A:1021801522545.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact