Document Open Access Logo

Heuristics for MDD Propagation in HADDOCK

Authors Rebecca Gentzel, Laurent Michel , Willem-Jan van Hoeve

PDF
Thumbnail PDF

File

LIPIcs.CP.2022.24.pdf
  • Filesize: 0.91 MB
  • 17 pages

Document Identifiers

Author Details

Rebecca Gentzel
  • University of Connecticut, Storrs, CT, USA
Laurent Michel
  • Synchrony Chair in Cybersecurity, University of Connecticut, Storrs, CT, USA
Willem-Jan van Hoeve
  • Carnegie Mellon University, Pittsburgh, PA, USA

Funding

Laurent Michel and Rebecca Gentzel were partially supported by Synchrony. Willem-Jan van Hoeve was partially supported by Office of Naval Research Grant No. N00014-21-1-2240 and National Science Foundation Award #1918102.

Cite AsGet BibTex

Rebecca Gentzel, Laurent Michel, and Willem-Jan van Hoeve. Heuristics for MDD Propagation in HADDOCK. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.CP.2022.24

Abstract

Haddock, introduced in [R. Gentzel et al., 2020], is a declarative language and architecture for the specification and the implementation of multi-valued decision diagrams. It relies on a labeled transition system to specify and compose individual constraints into a propagator with filtering capabilities that automatically deliver the expected level of filtering. Yet, the operational potency of the filtering algorithms strongly correlate with heuristics for carrying out refinements of the diagrams. This paper considers how to empower Haddock users with the ability to unobtrusively specify various such heuristics and derive the computational benefits of exerting fine-grained control over the refinement process.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Decision diagrams
  • Theory of computation → Constraint and logic programming
Keywords
  • Decision Diagrams

Metrics

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

Supplementary Materials

References

  1. Tobias Achterberg, Thorsten Koch, and Alexander Martin. Branching rules revisited. Operations Research Letters, 33, 2005. URL: https://doi.org/10.1016/j.orl.2004.04.002.
  2. H. R. Andersen, T. Hadzic, J. N. Hooker, and P. Tiedemann. A Constraint Store Based on Multivalued Decision Diagrams. In Proceedings of CP, volume 4741 of LNCS, pages 118-132. Springer, 2007. Google Scholar
  3. David L. Applegate, Robert E. Bixby, Vašek Chvátal, and William Cook. Finding cuts in the tsp. Annals of Physics, 54, 1995. Google Scholar
  4. N. Beldiceanu and E. Contejean. Introducing Global Constraints in CHIP. Journal of Mathematical and Computer Modelling, 20(12):97-123, 1994. Google Scholar
  5. Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: A methodological tour d’horizon. European Journal of Operational Research, 290:405-421, April 2021. URL: https://doi.org/10.1016/J.EJOR.2020.07.063.
  6. D. Bergman, A. A. Cire, W.-J. van Hoeve, and J. N. Hooker. Decision Diagrams for Optimization. Springer, 2016. Google Scholar
  7. Raphaël Boudreault and Claude-Guy Quimper. Improved cp-based lagrangian relaxation approach with an application to the tsp. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI, volume 21, pages 1374-1380, 2021. Google Scholar
  8. Frédéric Boussemart, Fred Hemery, and Christophe Lecoutre. Revision ordering heuristics for the constraint satisfaction problem. In First International Workshop: Constraint Propagation and Implementation, 2004. URL: http://www.cril.univ-artois.fr/~lecoutre/research/publications/2004/CPW2004.ps.
  9. T Fahle and M Sellman. Cost based filtering for the constrained knapsack problem. Annals of Operations Research, 115:73-93, 2002. Google Scholar
  10. J. M. Gauthier and G. Ribière. Experiments in mixed-integer linear programming using pseudo-costs. Mathematical Programming, 12, 1977. URL: https://doi.org/10.1007/BF01593767.
  11. R. Gentzel, L. Michel, and W.-J. van Hoeve. Haddock: A language and architecture for decision diagram compilation. In Principles and Practice of Constraint Programming. CP 2020, volume 12333 of Lecture Notes in Computer Science, pages 531-547. Springer, Cham, 2020. Google Scholar
  12. X. Gillard, P. Schaus, and Coppé. Ddo, a Generic and Efficient Framework for MDD-Based Optimization. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2020. Google Scholar
  13. Gilles Pesant Gilles, Claude Guy Quimper, and Alessandro Zanarini. Counting-based search: Branching heuristics for constraint satisfaction problems. Journal of Artificial Intelligence Research, 43, 2012. URL: https://doi.org/10.1613/jair.3463.
  14. T. Hadžić, J. N. Hooker, B. O'Sullivan, and P. Tiedemann. Approximate compilation of constraints into multivalued decision diagrams. In P. J. Stuckey, editor, Principles and Practice of Constraint Programming (CP 2008), volume 5202 of Lecture Notes in Computer Science, pages 448-462. Springer, 2008. Google Scholar
  15. R M Haralick and G L Elliot. Increasing tree search efficiency for constraint satisfaction problems. Artificial Intelligence, 14:263-313, 1980. Google Scholar
  16. S. Hoda, W.-J. van Hoeve, and J. N. Hooker. A Systematic Approach to MDD-Based Constraint Programming. In Proceedings of CP, volume 6308 of LNCS, pages 266-280. Springer, 2010. Google Scholar
  17. R. M. Keller. Formal Verification of Parallel Programs. Communications of the ACM, 19(7):371-384, 1976. Google Scholar
  18. M. Lagerkvist and C. Schulte. Propagator groups. In Ian Gent, editor, Fifteenth International Conference on Principles and Practice of Constraint Programming, Lisbon, Portugal, volume 5732 of Lecture Notes in Computer Science, pages 524-538. Springer-Verlag, 2009. Google Scholar
  19. Laurent Michel, Pierre Schaus, Pascal Van Hentenryck. MiniCP: A lightweight solver for constraint programming, 2018. Available from https://minicp.bitbucket.io. Google Scholar
  20. Jia Hui Liang, Vijay Ganesh, Pascal Poupart, and Krzysztof Czarnecki. Learning rate based branching heuristic for sat solvers. In Theory and Applications of Satisfiability Testing - SAT 2016 - 19th International Conference, Bordeaux, France, July 5-8, 2016, Proceedings, volume 9710, 2016. URL: https://doi.org/10.1007/978-3-319-40970-2_9.
  21. Laurent Michel and Pascal Van Hentenryck. Activity-based search for black-box constraint programming solvers. In Nicolas Beldiceanu, Narendra Jussien, and Éric Pinson, editors, Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems, volume 7298 of Lecture Notes in Computer Science, pages 228-243. Springer Berlin Heidelberg, 2012. URL: https://doi.org/10.1007/978-3-642-29828-8_15.
  22. Matthew W Moskewicz, Conor F Madigan, Ying Zhao, Lintao Zhang, and Sharad Malik. Chaff: engineering an efficient sat solver. In Proceedings of the 38th Design Automation Conference, DAC 2001, Las Vegas, NV, USA, June 18-22, 2001, pages 530-535. ACM, 2001. URL: https://doi.org/10.1145/378239.379017.
  23. Philippe Refalo. Impact-based search strategies for constraint programming. In Mark Wallace, editor, CP, volume 3258 of Lecture Notes in Computer Science, pages 557-571. Springer, 2004. URL: http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=3258&spage=557.
  24. Meinolf Sellmann, Thorsten Gellermann, and Robert Wright. Cost-based filtering for shorter path constraints. Constraints, 12, 2007. URL: https://doi.org/10.1007/s10601-006-9006-4.
  25. Guni Sharon, Roni Stern, Ariel Felner, and Nathan R. Sturtevant. Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence, 219, 2015. URL: https://doi.org/10.1016/j.artint.2014.11.006.
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 Imprint Privacy Contact