Correctness of Constraint Retraction Algorithms


Using a filtering technique is crucial to reduce the search space. Most of existing solvers (eg. CHIP, gnuProlog, Ilog Solver, CHOCO) use reduction operators and a propagation mechanisms to enforce a local consistency. This scheme is quite universally used on static CSPs. But we do not have such an unanimity when relaxing constraints. Several techniques have been proposed to deal with dynamicity. The problem we address here is two-fold. First, we introduce a general scheme for the existing techniques. Second, we present a sufficient set of properties to be enforced in order to incrementally relax constraints.