| Περίληψη: | In constraint programming there are often many choices regarding
the propagation method to be used on the constraints of a
problem. However, simple constraint solvers usually only apply a standard
method, typically (generalized) arc consistency, on all constraints
throughout search. Advanced solvers additionally allow for the modeler
to choose among an array of propagators for certain (global) constraints.
Since complex interactions exist among constraints, deciding in the modelling
phase which propagation method to use on given constraints can
be a hard task that ideally we would like to free the user from. In this paper
we propose a simple technique towards the automation of this task.
Our approach exploits information gathered from a random probing preprocessing
phase to automatically decide on the propagation method to
be used on each constraint. As we demonstrate, data gathered though
probing allows for the solver to accurately differentiate between constraints
that offer little pruning as opposed to ones that achieve many
domain reductions, and also to detect constraints and variables that are
amenable to certain propagation methods. Experimental results from an
initial evaluation of the proposed method on binary CSPs demonstrate
the benefits of our approach. |
|---|
English