STR3: A path-optimal filtering algorithm for table constraints

doi:10.1016/j.artint.2014.12.002

2015-03-01

PRE

Christophe Lecoutre

Chavalit Likitvivatanavong *

Roland H. C. Yap

DOI：10.1016/j.artint.2014.12.002

原文链接

原文求助

摘要

En 中文

Constraint propagation is a key to the success of Constraint Programming (CP). The principle is that filtering algorithms associated with constraints are executed in sequence until quiescence is reached. Many such algorithms have been proposed over the years to enforce the property called Generalized Arc Consistency (GAC) on many types of constraints, including table constraints that are defined extensionally. Recent advances in GAC algorithms for extensional constraints rely on directly manipulating tables during search. This is the case with a simple approach called Simple Tabular Reduction (STR), which systematically maintains tables of constraints to their relevant lists of tuples. In particular, STR2, a refined STR variant is among the most efficient GAC algorithms for positive table constraints. In this paper, we revisit this approach by proposing a new GAC algorithm called STR3 that is specifically designed to enforce GAC during backtrack search. By indexing tables and reasoning from deleted values, we show that STR3 can avoid systematically iterating over the full set of current tuples, contrary to STR2. An important property of STR3 is that it can completely avoid unnecessary traversal of tables, making it optimal along any path of the search tree. We also study a variant of STR3, based on an optimal circular way for traversing tables, and discuss the relationship of STR3 with two other optimal GAC algorithms introduced in the literature, namely, GAC4 and AC5TC-Tr. Finally, we demonstrate experimentally how STR3 is competitive with the state-of-the-art. In particular, our extensive experiments show that STR3 is generally faster than STR2 when the average size of tables is not reduced too drastically during search, making STR3 complementary to STR2. (C) 2014 Elsevier B.V. All rights reserved.

Keyword:

Constraint satisfaction problems

Generalized arc consistency

Non-binary constraints

Backtracking search