zbMATH — the first resource for mathematics

Generalized arc consistency for positive table constraints. (English) Zbl 1335.90096
Benhamou, Frédéric (ed.), Principles and practice of constraint programming – CP 2006. 12th international conference, CP 2006, Nantes, France, September 25–29, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-46267-5/pbk). Lecture Notes in Computer Science 4204, 284-298 (2006).
Summary: We propose a new algorithm to establish Generalized Arc Consistency (GAC) on positive table constraints, i.e. constraints defined in extension by a set of allowed tuples. Our algorithm visits the lists of valid and allowed tuples in an alternative fashion when looking for a support (i.e. a tuple that is both allowed and valid). It is then able to jump over sequences of valid tuples containing no allowed tuple and over sequences of allowed tuples containing no valid tuple. Our approach, that can be easily grafted to any generic GAC algorithm, admits on some instances a behaviour quadratic in the arity of the constraints whereas classical approaches, i.e. approaches that focus on either valid or allowed tuples, admit an exponential behaviour. We show the effectiveness of this approach, both theoretically and experimentally.
For the entire collection see [Zbl 1141.68004].

90C30 Nonlinear programming
Full Text: DOI