Abstract
This papers extends in three ways our previous work about efficient operations on Multi-valued Decision Diagrams (MDD) for building Constraint Programming models. First, we improve the existing methods for transforming a set of tuples, Global Cut Seeds or sequences of tuples into MDDs. Then, we present in-place algorithms for adding and deleting tuples from an MDD. Finally, we describe an incremental version of an algorithm which reduces an MDD. We show on a real-life application that in-place operations on MDDs combined with this incremental algorithm outperform classical operations. Furthermore, we give some experimental results showing that the creation algorithms we propose strongly improve upon existing ones.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Andersen, H.R., Hadzic, T., Hooker, J.N., Tiedemann, P.: A constraint store based on multivalued decision diagrams. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 118–132. Springer, Heidelberg (2007)
Bergman, D., Cire, A., van Hoeve, W.-J.: MDD propagation for sequence constraints. J. Artif. Intell. Res. 50, 697–722 (2014)
Bergman, D., van Hoeve, W.-J., Hooker, J.N.: Manipulating MDD relaxations for combinatorial optimization. In: Achterberg, T., Beck, J.C. (eds.) CPAIOR 2011. LNCS, vol. 6697, pp. 20–35. Springer, Heidelberg (2011)
Brace, K.S., Rudell, R.L., Bryant, R.E.: Efficient implementation of a BDD package. In: Proceedings of the 27th ACM/IEEE Design Automation Conference, pp. 40–45. ACM (1991)
Bryant, R.E.: Symbolic boolean manipulation with ordered binary decision diagrams. ACM Comput. Surv. 24(3), 293–318 (1992)
Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. C C35(8), 677–691 (1986)
Cheng, K., Yap, R.: An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints. Constraints 15, 265–304 (2010)
Cheng, K.C.K., Yap, R.H.C.: Maintaining generalized arc consistency on ad hoc r-ary constraints. In: Stuckey, P.J. (ed.) CP 2008. LNCS, vol. 5202, pp. 509–523. Springer, Heidelberg (2008)
Ciré, A.A., Hooker, J.N.: The separation problem for binary decision diagrams. In: International Symposium on Artificial Intelligence and Mathematics, ISAIM 2014, Fort Lauderdale, FL, USA, 6–8 January 2014
Focacci, F., Milano, M.: Global cut framework for removing symmetries. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 77–92. Springer, Heidelberg (2001)
Gange, G., Stuckey, P., Szymanek, R.: MDD propagators with explanation. Constraints 16, 407–429 (2011)
Gent, I., Jefferson, C., Miguel, I., Nightingale, P.: Data structures for generalised arc consistency for extensional constraints. In: Proceedings of AAAI 2007, pp. 191–197, Vancouver, Canada (2007)
Hadzic, T., Hooker, J.N., O’Sullivan, B., Tiedemann, P.: Approximate compilation of constraints into multivalued decision diagrams. In: Stuckey, P.J. (ed.) CP 2008. LNCS, vol. 5202, pp. 448–462. Springer, Heidelberg (2008)
Hoda, S., van Hoeve, W.-J., Hooker, J.N.: A systematic approach to MDD-based constraint programming. In: Cohen, D. (ed.) CP 2010. LNCS, vol. 6308, pp. 266–280. Springer, Heidelberg (2010)
Lhomme, O.: Practical reformulations with table constraints. In: ECAI, pp. 911–912 (2012)
Papadopoulos, A., Roy, P., Pachet, F.: Avoiding plagiarism in markov sequence generation. In: Proceeding of the Twenty-Eight AAAI Conference on Artificial Intelligence, pp. 2731–2737 (2014)
Perez, G., Régin, J.-C.: Improving GAC-4 for table and MDD constraints. In: O’Sullivan, B. (ed.) CP 2014. LNCS, vol. 8656, pp. 606–621. Springer, Heidelberg (2014)
Perez, G., Régin, J.-C.: Efficient operations on MDDs for building constraint programming models. In: International Joint Conference on Artificial Intelligence, IJCAI 2015, pp. 374–380, Argentina (2015)
Régin, J.-C.: Improving the expressiveness of table constraints. In: CP 2011, Proceedings Workshop ModRef 2011 (2011)
Srinivasan, A., Ham, T., Malik, S., Brayton, R.K.: Algorithms for discrete function manipulation. In: IEEE International Conference on Computer-Aided Design, ICCAD 1990. Digest of Technical Papers, pp. 92–95. IEEE (1990)
Acknowledgments
We would like to thank very much Laurent Perron and Christophe Lecoutre for their useful comments which helped to improve the paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Perez, G., Régin, JC. (2016). Constructions and In-Place Operations for MDDs Based Constraints. In: Quimper, CG. (eds) Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2016. Lecture Notes in Computer Science(), vol 9676. Springer, Cham. https://doi.org/10.1007/978-3-319-33954-2_20
Download citation
DOI: https://doi.org/10.1007/978-3-319-33954-2_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-33953-5
Online ISBN: 978-3-319-33954-2
eBook Packages: Computer ScienceComputer Science (R0)