The Regularization of Small Sub-Constraint Satisfaction Problems
This addresses efficiency issues in constraint solving for researchers and practitioners, though it appears incremental as it builds on existing methods.
The paper tackles optimization of constraint satisfaction problems by substituting sub-CSPs with regular membership constraints to reduce fails and improve propagation, resulting in faster resolution speeds and competitiveness with recent tabulation methods.
This paper describes a new approach on optimization of constraint satisfaction problems (CSPs) by means of substituting sub-CSPs with locally consistent regular membership constraints. The purpose of this approach is to reduce the number of fails in the resolution process, to improve the inferences made during search by the constraint solver by strengthening constraint propagation, and to maintain the level of propagation while reducing the cost of propagating the constraints. Our experimental results show improvements in terms of the resolution speed compared to the original CSPs and a competitiveness to the recent tabulation approach. Besides, our approach can be realized in a preprocessing step, and therefore wouldn't collide with redundancy constraints or parallel computing if implemented.