From MDD to BDD and arc consistency. (English) Zbl 1468.68209

Vion, Julien; Piechowiak, Sylvain

Constraints 23, No. 4, 451-480 (2018).

Summary: In this paper, we present a new conversion of multivalued decision diagrams (MDD) to binary decision diagrams (BDD) which can be used to improve MDD-based filtering algorithms such as MDDC or MDD-4R. We also propose BDDF, an algorithm that copies modified parts of the BDD “on the fly” during the search of a solution, and yields a better incrementality than a pure MDDC-like approach. MDDC is not very efficient when used to represent poorly structured positive table constraints. Our new representation combined with BDDF retains the properties of the MDD representation and has comparable performances to the STR2 algorithm by J. R. Ullmann [Inf. Sci. 177, No. 18, 3639–3678 (2007; Zbl 1119.68446)] and C. Lecoutre [Constraints 16, No. 4, 341–371 (2011; Zbl 1244.90232)].

MSC:

68T20

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Keywords:

propagation; filtering; table constraints; binary decision diagram; multivalued decision diagram

Citations:

Zbl 1119.68446; Zbl 1244.90232

Software:

Concrete; STR2; Scala; MiniZinc; GitHub

References:

[1]	Allen, J. (1978). Anatomy of LISP. New York: McGraw-Hill, Inc. isbn: 0-07-001115-X. · Zbl 0424.68012
[2]	Bagwell, P. (2001). Ideal hash trees. Tech. rep EPFL.
[3]	Bentley, J., & Floyd, R.W. (1987). Programming pearls: a sample of brilliance. In Commun (Vol. 30.9, pp. 754-757), ACM.
[4]	Bergman, D., Ciré, A.A., van Hoeve, W.-J., Hooker, J. (2016). MDD Propagation for sequence constraints. In Decision diagrams for optimization (Chap. 10, pp. 183-204). Springer.
[5]	Bessière, C., & Régin J.-C. (1996). MAC and combined heuristics: two reasons to forsake FC (and CBJ?) on hard problems. In Proc. of the 12th itl. conf. on principle and practice of constraint programming (CP) (pp. 61-75).
[6]	Bollig, B., & Wegener, I. (1996). Improving the variable ordering of OBDDs is NP-complete. In IEEE Transactions on computers (Vol. 45.9, pp. 993-1002). · Zbl 1048.68571
[7]	Briggs, P., & Torczon, L. (1993). An efficient representation for sparse sets. In ACM Letters on programming languages and systems (Vol. 2.1-4, pp. 59-69).
[8]	Bryant, R.E. (1986). Graph-based algorithms for boolean function manipulation. In IEEE Transactions on computers 100.8 (pp. 677-691). · Zbl 0593.94022
[9]	Cheng, K.C.K., & Yap, R.H.C. (2010). An MDD-based GAC algorithm for positive and negative table constraints and some global constraints. In Constraints (Vol. 15.2, pp. 265-304). · Zbl 1204.68188
[10]	Cheng, K.C.K., & Yap, R.H.C. (2006). Maintaining generalized arc consistency on ad-hoc n-ary boolean constraints. In Proc. ECAI-06 (pp. 78-82). IOS Press.
[11]	Ciré, A.A., & Hooker, J.N. (2014). The separation problem for binary decision diagrams. In Proc. ISAIM.
[12]	Codd, E.F. (1970). A relational model of data for large shared data banks. In Communications of the ACM (Vol. 13.6, pp. 377-387). · Zbl 0207.18003
[13]	Demeulenaere, J., Hartert, R., Lecoutre, C., Perez, G., Perron, L., Régin, J., Schaus, P. (2016). Compact-table: efficiently filtering table constraints with reversible sparse bit-sets. In Proc. CP’2016, (Vol. 9892 pp. 207-223): LNCS. Springer.
[14]	Driscoll, JR; Sarnak, N.; Sleator, D.; Tarjan, R., Making data structures persistent, Journal of Computer and System Science, 38, 86-124, (1989) · Zbl 0667.68026
[15]	Fredkin, E. (1960). Trie memory. In Comm. ACM (Vol. 3.9, pp. 490-499).
[16]	Gange, G., Stuckey, P.J., Szymanek, R. (2011). MDD propagators with explanation. In Constraints (Vol. 16.4, pp. 407-429). · Zbl 1241.90066
[17]	Gent, I.P., Jefferson, C, Miguel, I., Nightingale, P. (2007). Data structures for generalised arc consistency for extensional constraints. In Proc. AAAI’2007 (pp. 191-197).
[18]	Gent, I.P., & Walsh, T. (1999). CSPLib: a benchmark library for constraints. Tech. rep. APES-09-1999. http://www.csplib.org.
[19]	Hadzic, T., Hansen, E.R., O’Sullivan, B. (2008). On automata, MDDs and BDDs in constraint satisfaction. In Proc. ECAI Workshop on inference methods based on graphical structure of knowledge (WIGSK).
[20]	Hentenryck, P.; Deville, Y.; Teng, CM, A generic AC algorithm and its specializations, Artificial Intelligence, 57, 291-321, (1992) · Zbl 0763.68059
[21]	Lecoutre, C. (2006). Benchmarks 2.0 XML representation of CSP instances. http://www.cril.univ-artois.fr/lecoutre/research/benchmarks.
[22]	Lecoutre, C., STR2: optimized simple tabular reduction for table constraints, Constraints, 16.4, 341-371, (2011) · Zbl 1244.90232
[23]	Lecoutre, C., & Hemery, F. (2007). A study of residual supports in arc consistency. In Proceedings of IJCAI’2007 (pp. 125-130).
[24]	Lecoutre, C., Likitvivatanavong, C., Yap, R.H.C. (2012). A path-optimal GAC algorithm for table constraints. In Proc. ECAI’2012 (pp. 510-515). · Zbl 1327.68220
[25]	Lecoutre, C., & Roussel, O. (2008). XML representation of constraint networks, Version 2.1. In The Computing research repository arXiv:0902.2362v1.
[26]	Mackworth, AK, Consistency in networks of relations, Artificial Intelligence, 8.1, 99-118, (1977) · Zbl 0341.68061
[27]	Mairy, J-B; Hentenryck, P.; Deville, Y., Optimal and efficient filtering algorithms for table constraints, Constraints, 19.1, 77-120, (2014) · Zbl 1328.68201
[28]	Michie, D., Memo functions and machine learning, Nature, 218, 19-22, (1968)
[29]	Montanari, U., Network of constraints: fundamental properties and applications to picture processing, Information Science, 7, 95-132, (1974) · Zbl 0284.68074
[30]	Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G. (2007). Minizinc: towards a standard CP modelling language. In Bessière, C. (Ed.) Proc. CP’2007 (pp. 529-543): LNCS 4741. Springer-Verlag.
[31]	Odersky, M., & et al. (2001). The scala programming language. http://www.scalalang.org/.
[32]	Perez, G., & Régin, J.-C. (2015). Efficient operations on MDDs for building constraint programming models. In Proc. 24th IJCAI (pp. 374-380).
[33]	Perez, G., & Régin, J.-C. (2014). Improving GAC-4 for table and MDD constraints. In O’Sullivan, B. (Ed.) Proc. 20th Conference on principles and practice of CP (pp. 606-621): LNCS 8656. Springer.
[34]	Srinivasan, A., Ham, T., Malik, S., Brayton, R.K. (1990). Algorithms for discrete function manipulation. In 1990 IEEE International conference on computer-aided design. Digest of Technical Papers. pp. 92-95. https://doi.org/10.1109/ICCAD.1990.129849.
[35]	Stuckey, PJ; Feydy, T.; Schutt, A.; Tack, G.; Fischer, J., The minizinc challenge 2008-2013, AI Magazine, 35.2, 55-60, (2014)
[36]	Ullmann, JR, Partition search for non-binary constraint satisfaction, Information Science, 177, 3639-3678, (2007) · Zbl 1119.68446
[37]	Vion, J. (2006). Concrete: a CSP Solving API for the JVM. http://github.com/concrete-cp.
[38]	Vion, J. (2013). Consistance d’arc par MDD-Réduction. French. In Truchet, C. (ed) Actes des 9\(e\)Journées Francophones de Programmation par Contraintes (JFPC) (pp. 323-332).
[39]	Vion, J., & Piechowiak, S. (2014). Maintenir des MDD persistants pour établir la consistance d’arc. French. In Revue d’Intelligence Artificielle (Vol. 28.5, pp. 547-569).
[40]	Xu, K.; Boussemart, F.; Hemery, F.; Lecoutre, C., A simple model to generate hard satisfiable instances, Artificial Intelligence, 171, 514-534, (2007) · Zbl 1168.68554