Document Open Access Logo

Peel-And-Bound: Generating Stronger Relaxed Bounds with Multivalued Decision Diagrams

Authors Isaac Rudich, Quentin Cappart, Louis-Martin Rousseau

PDF
Thumbnail PDF

File

LIPIcs.CP.2022.35.pdf
  • Filesize: 1.29 MB
  • 20 pages

Document Identifiers

Author Details

Isaac Rudich
  • Mathematics and Industrial Engineering Department, Polytechnique Montréal, Canada
Quentin Cappart
  • Computer Engineering and Software Engineering Department, Polytechnique Montréal, Canada
Louis-Martin Rousseau
  • Mathematics and Industrial Engineering Department, Polytechnique Montréal, Canada

Cite As Get BibTex

Isaac Rudich, Quentin Cappart, and Louis-Martin Rousseau. Peel-And-Bound: Generating Stronger Relaxed Bounds with Multivalued Decision Diagrams. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CP.2022.35

Abstract

Decision diagrams are an increasingly important tool in cutting-edge solvers for discrete optimization. However, the field of decision diagrams is relatively new, and is still incorporating the library of techniques that conventional solvers have had decades to build. We drew inspiration from the warm-start technique used in conventional solvers to address one of the major challenges faced by decision diagram based methods. Decision diagrams become more useful the wider they are allowed to be, but also become more costly to generate, especially with large numbers of variables. We present a method of peeling off a sub-graph of previously constructed diagrams and using it as the initial diagram for subsequent iterations that we call peel-and-bound. We test the method on the sequence ordering problem, and our results indicate that our peel-and-bound scheme generates stronger bounds than a branch-and-bound scheme using the same propagators, and at significantly less computational cost.

Subject Classification

ACM Subject Classification
  • Applied computing → Operations research
Keywords
  • decision diagrams
  • discrete optimization
  • branch-and-bound
  • sequencing
  • constraint programming

Metrics

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

Supplementary Materials

References

  1. Henrik Andersen, Tarik Hadzic, John Hooker, and Peter Tiedemann. A constraint store based on multivalued decision diagrams. In Bessière, C. (eds) Principles and Practice of Constraint Programming – CP 2007, volume 4741 of Lecture Notes in Computer Science, pages 118-132, September 2007. Google Scholar
  2. Philippe Baptiste, Claude Le Pape, and Wim Nuijten. Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. International Series in Operations Research and Management Science, Kluwer. Springer International Publishing, 2001. Google Scholar
  3. David Bergman, Andre Cire, Willem-Jan van Hoeve, and John Hooker. Decision Diagrams for Optimization. Springer International Publishing, January 2016. Google Scholar
  4. David Bergman, Andre Cire, Willem-Jan van Hoeve, and John Hooker. Discrete optimization with decision diagrams. INFORMS Journal on Computing, 28:47-66, February 2016. Google Scholar
  5. David Bergman, André A. Cire, Ashish Sabharwal, Horst Samulowitz, Vijay Saraswat, and Willem-Jan van Hoeve. Parallel combinatorial optimization with decision diagrams. Proceedings of the International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pages 351-367, 2014. Google Scholar
  6. Quentin Cappart, Emmanuel Goutierre, David Bergman, and Louis-Martin Rousseau. Improving optimization bounds using machine learning: Decision diagrams meet deep reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1443-1451, 2019. Google Scholar
  7. Margarita Castro, Chiara Piacentini, Andre Cire, and J. Beck. Solving delete free planning with relaxed decision diagram based heuristics. Journal of Artificial Intelligence Research, 67:607-651, March 2020. Google Scholar
  8. Margarita P. Castro, Andre A. Cire, and J. Christopher Beck. Decision diagrams for discrete optimization: A survey of recent advances, 2022. URL: http://arxiv.org/abs/2201.11536.
  9. André A. Cire and Willem-Jan van Hoeve. Multivalued decision diagrams for sequencing problems. Operations Research, 61(6):1259, 1462, 2013. Google Scholar
  10. Xavier Gillard, Vianney Coppé, Pierre Schaus, and André A. Cire. Improving the filtering of branch-and-bound mdd solver. Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 18th International Conference, CPAIOR 2021, 2021. Google Scholar
  11. Jaime González, Andre Cire, Andrea Lodi, and Louis-Martin Rousseau. Integrated integer programming and decision diagram search tree with an application to the maximum independent set problem. Constraints, 25, April 2020. Google Scholar
  12. Tarik Hadzic, John Hooker, Barry O'Sullivan, and Peter Tiedemann. Approximate compilation of constraints into multivalued decision diagrams. In Stuckey, P.J. (eds) Principles and Practice of Constraint Programming. CP 2008, Lecture Notes in Computer Science, pages 448-462, September 2008. Google Scholar
  13. Samid Hoda, Willem-Jan van Hoeve, and John Hooker. A systematic approach to mdd-based constraint programming. In Cohen, D. (eds) Principles and Practice of Constraint Programming – CP 2010. CP 2010, volume 6308 of Lecture Notes in Computer Science, pages 266-280, September 2010. Google Scholar
  14. Willem-Jan Hoeve. Graph coloring with decision diagrams. Mathematical Programming, May 2021. Google Scholar
  15. John Hooker. Decision diagrams and dynamic programming. In Gomes, C., Sellmann, M. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2013, volume 7874 of Lecture Notes in Computer Science, May 2013. Google Scholar
  16. John Hooker. Job sequencing bounds from decision diagrams. In Beck, J. (eds) Principles and Practice of Constraint Programming. CP 2017, Lecture Notes in Computer Science, pages 565-578, August 2017. Google Scholar
  17. John Hooker. Improved job sequencing bounds from decision diagrams. In Schiex, T., de Givry, S. (eds) Principles and Practice of Constraint Programming. CP 2019, volume 11802 of Lecture Notes in Computer Science, pages 268-283, September 2019. URL: https://doi.org/10.1007/978-3-030-30048-7_16.
  18. Anthony Karahalios and Willem-Jan Hoeve. Variable ordering for decision diagrams: A portfolio approach. Constraints, pages 1-18, January 2022. Google Scholar
  19. Anna Latour, Behrouz Babaki, and Siegfried Nijssen. Stochastic constraint propagation for mining probabilistic networks. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, pages 1137-1145, August 2019. Google Scholar
  20. Leonardo Lozano and J. Smith. A binary decision diagram based algorithm for solving a class of binary two-stage stochastic programs. Mathematical Programming, August 2018. Google Scholar
  21. Johannes Maschler and Günther Raidl. Multivalued decision diagrams for prize-collecting job sequencing with one common and multiple secondary resources. Annals of Operations Research, 302, July 2021. Google Scholar
  22. Augustin Parjadis, Quentin Cappart, Louis-Martin Rousseau, and David Bergman. Improving branch-and-bound using decision diagrams and reinforcement learning. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 446-455. Springer, 2021. Google Scholar
  23. Guillaume Perez and Jean-Charles Régin. Parallel algorithms for operations on multi-valued decision diagrams. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), April 2018. Google Scholar
  24. Gerhard Reinelt. Tsplib. a traveling salesman problem library. INFORMS Journal on Computing, 3:376-384, November 1991. Google Scholar
  25. Thiago Serra and John Hooker. Compact representation of near-optimal integer programming solutions. Mathematical Programming, 182, April 2019. Google Scholar
  26. Diego Uña, Graeme Gange, Peter Schachte, and Peter Stuckey. Compiling cp subproblems to mdds and d-dnnfs. Constraints, 24, January 2019. Google Scholar
  27. Hélène Verhaeghe, Christophe Lecoutre, and Pierre Schaus. Compact-mdd: Efficiently filtering (s)mdd constraints with reversible sparse bit-sets. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, pages 1383-1389, July 2018. Google Scholar
  28. Julien Vion and Sylvain Piechowiak. From mdd to bdd and arc consistency. Constraints, 23, October 2018. Google Scholar
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