×

On the reification of global constraints. (English) Zbl 1328.68192

Summary: We introduce a simple idea for deriving reified global constraints in a systematic way. It is based on the observation that most global constraints can be reformulated as a conjunction of total function constraints together with a constraint that can be easily reified.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68N17 Logic programming
68Q45 Formal languages and automata

Software:

MINION; Gecode; Zinc
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alvarez Divo, C.E. (2011). Automated reasoning on feature models via constraint programming. Master’s thesis, Uppsala University, Sweden. Tech. Rep. IT 11 041.
[2] Beldiceanu, N., Carlsson, M., Flener, P., Pearson, J. (2012). On the reification of global constraints. Tech. Rep. T2012:02, Swedish Institute of Computer Science. Available at http://soda.swedish-ict.se/view/sicsreport/ . · Zbl 1328.68192
[3] Beldiceanu, N., Carlsson, M., Petit, T. (2004). Deriving filtering algorithms from constraint checkers. In CP 2004. LNCS (Vol. 3258, pp. 107–122). Springer. · Zbl 1152.68539
[4] Beldiceanu, N., Carlsson, M., Rampon, J.X. (2012). Global constraint catalog, 2nd edn. (revision a). Tech. Rep. T2012:03, Swedish Institute of Computer Science.
[5] Beldiceanu, N., & Simonis, H. (2011). A constraint seeker: Finding and ranking global constraints from examples. In J.H.M. Lee (Ed.), CP 2011. LNCS (Vol. 6876). Springer.
[6] Bessière, C., Katsirelos, G., Narodytska, N., Quimper, C.G., Walsh, T. (2009). Decompositions of all different, global cardinality and related constraints. In IJCAI (pp. 419–424).
[7] Feydy, T., Somogyi, Z., Stuckey, P.J. (2011). Half reification and flattening. In J.H.M. Lee (Ed.), CP 2011. LNCS (Vol. 6876, pp. 286–301). Springer.
[8] Gent, I.P., Jefferson, C., Miguel, I. (2006). Minion: a fast scalable constraint solver. In ECAI 2006 (pp. 98–102). IOS Press.
[9] Jefferson, C., Moore, N.C.A., Nightingale, P., Petrie, K.E. (2010). Implementing logical connectives in constraint programming. Artificial Intelligence, 174, 1407–1429. · Zbl 1210.68103 · doi:10.1016/j.artint.2010.07.001
[10] Lazaar, N. (2011). Méthodologie et outil de test, de localisation de fautes et de correction automatique des programmes à contraintes. Ph.D. thesis, Rennes 1 Univ., France.
[11] Marriott, K., Nethercote, N., Rafeh, R., Stuckey, P.J., de la Banda, M.G., Wallace, M. (2008). The design of the Zinc modelling language. Constraints, 13(3), 229–267. · Zbl 1146.68352 · doi:10.1007/s10601-008-9041-4
[12] Pesant, G. (2004). A regular language membership constraint for finite sequences of variables. In M.G. Wallace (Ed.), CP 2004. LNCS 2004 (Vol. 3258, pp. 482–495). Springer. · Zbl 1152.68573
[13] Schulte, C., Tack, G., Lagerkvist, M.Z. (2011). Modeling and programming with gecode (version 3.7.1). Available from http://www.gecode.org/ .
[14] Van Hentenryck, P., & Deville, Y. (1991). The cardinality operator: a new logical connective in constraint logic programming. In ICLP 1991. MIT Press · Zbl 0789.68021
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.