Francis, Kathryn Glenn; Stuckey, Peter J. Explaining circuit propagation. (English) Zbl 1310.05144 Constraints 19, No. 1, 1-29 (2014). Summary: The circuit constraint is used to constrain a graph represented by a successor for each node, such that the resulting edges form a circuit. Circuit and its variants are important for various kinds of tour-finding, path-finding and graph problems. In this paper we examine how to integrate the circuit constraint, and its variants, into a lazy clause generation solver. To do so we must extend the constraint to explain its propagation. We consider various propagation algorithms for circuit and examine how best to explain each of them. We compare the effectiveness of each propagation algorithm once we use explanation, since adding explanation changes the trade-off between propagation complexity and power. Simpler propagators, although less powerful, may produce more reusable explanations. Even though the most powerful propagator considered for circuit and variants creates huge explanations, we find that explanation is highly advantageous for solving problems involving this kind of constraint. Cited in 3 Documents MSC: 05C62 Graph representations (geometric and intersection representations, etc.) 05C82 Small world graphs, complex networks (graph-theoretic aspects) 05C38 Paths and cycles Keywords:circuit; constraint propagation; explanation Software:Zinc; Chaff; MiniZinc; Gecode PDFBibTeX XMLCite \textit{K. G. Francis} and \textit{P. J. Stuckey}, Constraints 19, No. 1, 1--29 (2014; Zbl 1310.05144) Full Text: DOI Link References: [1] Beldiceanu, N., & Contejean, E. (1994). Introducing global constraints in CHIP. Mathematical and Computer Modelling, 20(12), 97-123. · Zbl 0816.68048 [2] Beldiceanu, N.; Flener, P.; Lorca, X., The tree constraint, No. 3524, 64-78 (2005), Berlin, Heidelberg · Zbl 1133.90403 [3] Beldiceanu, N., Flener, P., Lorca, X. (2008). Combining tree partitioning, precedence, and incomparability constraints. Constraints, 13(4), 459-489. · Zbl 1162.05321 [4] Caseau, Y., & Laburthe, F. (1997). Solving small TSPs with constraints. In Proceedings of the 14th international conference on logic programming (ICLP97) (pp. 316-330). · Zbl 1192.68654 [5] cycle constraint. Global constraint catalog: http://www.emn.fr/z-info/sdemasse/gccat/Ccycle.html. Accessed Dec 2012 [6] Downing, N.; Feydy, T.; Stuckey, P., Explaining alldifferent, No. 122, 115-124 (2012), Melbourne, Australia [7] Fages, J.; Lorca, X., Revisiting the tree constraint, No. 6876, 271-285 (2011), Berlin, Heidelberg [8] Fages, J., & Lorca, X. (2012). Improving the asymmetric TSP by considering graph structure. arXiv:1206.3437. · Zbl 1133.90403 [9] Katsirelos, G. (2008). Nogood processing in CSPs. PhD thesis, University of Toronto. · Zbl 1146.68352 [10] Katsirelos, G., & Bacchus, F. (2005). Generalized nogoods in CSPs. In Proceedings, the 20th national conference on artificial intelligence and the 17th innovative applications of artificial intelligence conference, 9-13 July 2005, Pittsburgh, Pennsylvania, USA (pp. 390-396). [11] Kaya, L.; Hooker, J., A filter for the circuit constraint, No. 4204, 706-710 (2006), Berlin, Heidelberg · Zbl 1119.93409 [12] Marriott, K., Nethercote, N., Rafeh, R., Stuckey, P., Garcia de la Banda, M., Wallace, M. (2008). The design of the zinc modelling language. Constraints, 13(3), 229-267. · Zbl 1146.68352 [13] Moskewicz, M., Madigan, C., Zhao, Y., Zhang, L., Malik, S. (2001). Chaff: Engineering an efficient SAT solver. In Proceedings of 38th conference on design automation (DAC’01) (pp. 530-535). [14] Nethercote, N., Stuckey, P., Becket, R., Brand, S., Duck, G., Tack, G. (2007). Minizinc: Towards a standard CP modelling language. In C. Bessiere (Ed.), Proceedings of the 13th international conference on principles and practice of constraint programming. LNCS (Vol. 4741, pp. 529-543). Springer-Verlag. [15] Ohrimenko, O., Stuckey, P., Codish, M. (2009). Propagation via lazy clause generation. Constraints, 14(3), 357-391. · Zbl 1192.68654 [16] Quesada, L., Van Roy, P., Deville, Y., Collet, R. (2006). Using dominators for solving constrained path problems. In Practical aspects of declarative languages, proceedings 8th international symposium, PADL 2006, Charleston, SC, USA, 9-10 January 2006. Lecture notes in computer science (Vol. 3819, pp. 73-87). [17] Schulte, C., & Stuckey, P. (2008). Efficient constraint propagation engines. ACM Transactions on Programming Languages and Systems, 31(1), Article No. 2. [18] Schulte, C., & Tack, G. (2009). Weakly monotonic propagators. In Principles and practice of constraint programming-CP 2009 (pp. 723-730). [19] Schulte, C., Lagerkvist, M., Tack, G. GECODE—an open, free, efficient constraint solving toolkit. http://www.gecode.org/. Accessed Dec 2012 · Zbl 0251.05107 [20] Tarjan, R. (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146-160. · Zbl 0251.05107 [21] van Hoeve, W. (2001). The alldifferent constraint: A survey. arXiv:cs/0105015. Accessed Dec 2012 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.