Search

Constraint propagation solvers interleave propagation, removing impossible values from variable domains, with search. The solver state is modified during propagation. But search requires the solver to return to a previous state. Hence a propagation solver must determine how to maintain state during propagation and forward and backward search. This paper sets out the possible ways in which a propagation solver can choose to maintain state, and the restrictions that such choices place on the resulting system. Experiments illustrate the result of various choices for the three principle state components of a solver: variables, propagators, and dependencies between them. This paper also provides the first realistic comparison of trailing versus copying for state restoration. [ABSTRACT FROM AUTHOR]

Today΄s models for propagation-based constraint solvers require propagators as implementations of constraints to be at least contracting and monotonic. These models do not comply with reality: today΄s constraint programming systems actually use non-monotonic propagators. This paper introduces the first realistic model of constraint propagation by assuming a propagator to be weakly monotonic (complying with the constraint it implements). Weak monotonicity is shown to be the minimal property that guarantees constraint propagation to be sound and complete. The important insight is that weak monotonicity makes propagation in combination with search well behaved. A case study suggests that non-monotonicity can be seen as an opportunity for more efficient propagation. [ABSTRACT FROM AUTHOR]

When implementing a propagator for a constraint, one must decide about variants: When implementing min , should one also implement max ? Should one implement linear equations both with and without coefficients? Constraint variants are ubiquitous: implementing them requires considerable effort, but yields better performance. This paper shows how to use variable views to derive perfect propagator variants: derived propagators inherit essential properties such as correctness and domain and bounds completeness. [ABSTRACT FROM AUTHOR]

This paper introduces an architecture for generic constraint implementations based on variable views and range iterators. Views allow, for example, to scale, translate, and negate variables. The paper shows how to make constraint implementations generic and how to reuse a single generic implementation with different views for different constraints. A wide range of applications of views exemplifies their usefulness and their potential for simplifying constraint implementations. We introduce domain operations compatible with views based on range iterators. The paper evaluates the applicability of the approach as well as different implementation techniques for the presented architecture. [ABSTRACT FROM AUTHOR]

Ideally, programming propagators as implementations of constraints should be an entirely declarative specification process for a large class of constraints: a high-level declarative specification is automatically translated into an efficient propagator. This paper introduces the use of existential monadic second-order logic as declarative specification language for finite set propagators. The approach taken in the paper is to automatically derive projection propagators (involving a single variable only) implementing constraints described by formulas. By this, the paper transfers the ideas of indexicals to finite set constraints while considerably increasing the level of abstraction available with indexicals. The paper proves soundness and completeness of the derived propagators and presents a run-time analysis, including techniques for efficiently executing projectors for n-ary constraints. [ABSTRACT FROM AUTHOR]

This paper introduces an architecture for generic constraint implementations based on variable views and range iterators. Views allow, for example, to scale, translate, and negate variables. The paper shows how to make constraint implementations generic and how to reuse a single generic implementation with different views for different constraints. Applications of views exemplify their usefulness and their potential for simplifying constraint implementations. We introduce domain operations compatible with views based on range iterators to access and modify entire variable domains. [ABSTRACT FROM AUTHOR]

Search is essential for constraint programming. Search engines typically combine several features like state restoration for backtracking, best solution search, parallelism, or visualization. In current implementations like Mozart, however, these search engines are monolithic and hard-wired to one exploration strategy, severely complicating the implementation of new exploration strategies and preventing their reuse. This paper presents the design of a search factory for Mozart, a program that enables the user to freely combine several orthogonal aspects of search, resulting in a search engine tailored to the user's needs. The abstractions developed here support fully automatic recomputation with last alternative optimization. They present a clean interface, making the implementation of new exploration strategies simple. Conservative extensions of the abstractions are presented that support best solution search and parallel search as orthogonal modules. IOzSeF, the Interactive Oz Search Factory, implements these abstractions and is freely available for download. [ABSTRACT FROM AUTHOR]