An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints.

*(English)*Zbl 1204.68188Summary: A table constraint is explicitly represented as its set of solutions or non-solutions. This ad hoc (or extensional) representation may require space exponential to the arity of the constraint, making enforcing GAC expensive. In this paper, we address the space and time inefficiencies simultaneously by presenting the MDDC constraint. MDDC is a global constraint that represents its (non-)solutions with a Multi-Valued Decision Diagram (MDD). The MDD-based representation has the advantage that it can be exponentially smaller than a table. The associated GAC algorithm (called MDDC) has time complexity linear to the size of the MDD, and achieves full incrementality in constant time. In addition, we show how to convert a positive or negative table constraint into an MDDC constraint in time linear to the size of the table. Our experiments on structured problems, car sequencing and still-life, show that MDDC is also a fast GAC algorithm for some global constraints such as sequence and regular. We also show that MDDC is faster than the state-of-the-art generic GAC algorithms in [I. P. Gent, C. Jefferson, I. Miguel and P. Nightingale, “Data structures for generalized arc consistency for extensional constraints”, in: National conference on artificial intelligence (2007)], [C. Lecoutre and R. Szymanek, “Generalized arc consistency for positive table constraints”, in: International conference on principles and practice of constraint programming (2006)], and [O. Lhomme and J. C. Régin, “A fast arc consistency algorithm for \(n\)-ary constraints”, in: National conference on artificial intelligence (2005)] for table constraint.

##### MSC:

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

##### Keywords:

ad hoc constraint; global constraint; table constraint; positive constraint; negative constraint; multi-valued decision diagram; generalized arc consistency
PDF
BibTeX
XML
Cite

\textit{K. C. K. Cheng} and \textit{R. H. C. Yap}, Constraints 15, No. 2, 265--304 (2010; Zbl 1204.68188)

Full Text:
DOI

##### References:

[1] | Beldiceanu, N., & Contejean, E. (1994). Introducing global constraints in CHIP. Journal of Mathematical and Computer Modelling, 20(12), 97–123. · Zbl 0816.68048 · doi:10.1016/0895-7177(94)90127-9 |

[2] | Bessière, C., & Régin, J.-C. (1997). Arc consistency for general constraint networks: Preliminary results. In International joint conference on artificial intelligence (pp. 398–404). |

[3] | Bessière, C., & Régin, J.-C. (1999). Enforcing arc consistency on global constraints by solving subproblems on the fly. In International Conference on Principles and Practice of Constraint Programming (pp. 103–117). · Zbl 0961.68124 |

[4] | Bessière, C., Régin, J.-C., Yap, R. H. C., & Zhang, Y. (2005). An optimal coarse-grained arc consistency algorithm. Artificial Intelligence, 165(2), 165–185. · Zbl 1132.68691 · doi:10.1016/j.artint.2005.02.004 |

[5] | Bollig, B., & Wegener, I. (1996). Improving the variable ordering of OBDDs is NP-complete. IEEE Transactions on Computers, 45(9), 993–1002. · Zbl 1048.68571 · doi:10.1109/12.537122 |

[6] | Briggs, P., & Torczon, L. (1993). An efficient representation for sparse sets. ACM Letters on Programming Languages and Systems, 2(1–4), 59–69. · doi:10.1145/176454.176484 |

[7] | Bryant, R. E. (1986). Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, 35(8), 667–691. · Zbl 0593.94022 · doi:10.1109/TC.1986.1676819 |

[8] | Carlsson, M. (2006). Filtering for the case constraint. Talk given at Advanced School on Global Constraints. |

[9] | Carlsson, M., et al. (2005). SICStus Prolog User’s Manual. Swedish Institute of Computer Science, release 3.12.3 ed. http://www.sics.se/sicstus/ . |

[10] | Cheng, K. C. K., & Yap, R. H. C. (2006a). Applying ad-hoc global constraints with the case constraint to Still-life. Constraints, 11(2–3), 91–114. · Zbl 1103.68807 · doi:10.1007/s10601-006-8058-9 |

[11] | Cheng, K. C. K., & Yap, R. H. C. (2006b). Maintaining generalized arc consistency on ad-hoc n-ary boolean constraints. In European conference on artificial intelligence (pp. 78–82). |

[12] | Cheng, K. C. K., & Yap, R. H. C. (2008). Maintaining generalized arc consistency on ad hoc r-ary constraints. In International conference on principles and practice of constraint programming (pp. 509–523). |

[13] | Dincbas, M., Simonis, H., & van Hentenryck, P. (1988). Solving the car-sequencing problem in constraint logic programming. In European conference on artificial intelligence (pp. 290–295). |

[14] | Eén, N., & Sörensson, N. (2006). Translating pseudo-boolean constraints into SAT. Journal on Satisiability, Boolean Modeling and Computation, 2, 1–26. · Zbl 1116.68083 |

[15] | Gent, I. P., Jefferson, C., Miguel, I., & Nightingale, P. (2007). Data structures for generalized arc consistency for extensional constraints. In National conference on artificial intelligence. |

[16] | Guy, R., Conway, J. H., & Berlekamp, E. (1982). Winning ways: for your mathematical plays (Vol. 2). London: Academic Press. · Zbl 0485.00025 |

[17] | Katsirelos, G., & Walsh, T. (2007). A compression algorithm for large arity extensional constraints. In International conference on principles and practice of constraint programming (pp. 379–393). |

[18] | Lecoutre, C. (2008). Optimization of simple tabular reduction for table constraints. In International conference on principles and practice of constraint programming (pp. 128–143). |

[19] | Lecoutre, C., & Szymanek, R. (2006). Generalized arc consistency for positive table constraints. In International conference on principles and practice of constraint programming (pp. 284–298). · Zbl 1335.90096 |

[20] | Lhomme, O. (2004). Arc-consistency filtering algorithm for logical combinations of constraints. In International conference on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (pp. 209–224). · Zbl 1094.68648 |

[21] | Lhomme, O., & Régin, J.-C. (2005). A fast arc consistency algorithm for n-ary constraints. In National conference on artificial intelligence (pp. 405–410). |

[22] | Mackworth, A. K. (1977). On reading sketch maps. In International joint conference on artificial intelligence (pp. 598–606). |

[23] | Pesant, G. (2004). A regular language membership constraint for finite sequences of variables. In International conference on principles and practice of constraint programming (pp. 482–495). · Zbl 1152.68573 |

[24] | Srinivasan, A., Kam, T., Malik, S., & Brayton, R. (1990). Algorithms for discrete function manipulation. In Computer aided design (pp. 92–95). |

[25] | Ullmann, J. R. (2007). Partition search for non-binary constraint satisfaction. Information Science, 177, 3639–3678. · Zbl 1119.68446 · doi:10.1016/j.ins.2007.03.030 |

[26] | van Hoeve, W.-J., Pesant, G., Rousseau, L.-M., & Sabharwal, A. (2006). Revisiting the sequence constraint. In International conference on principles and practice of constraint programming (pp. 620–634). · Zbl 1160.68573 |

[27] | Xu, K., Boussemart, F., Hemery, F., & Lecoutre, C. (2005). A simple model to generate hard satisfiable instances. In International joint conference on artificial intelligence (pp. 337–342). |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.