Constraint programming (CP) has been extensively used to solve a wide variety of problems. Its declarative flavor makes possible to state conditions over variables and the solver finds solutions by applying generic and complete techniques. The process of computing a solution in CP consists mainly in two phases: propagation in which values that are not consistent w.r.t. the constraints are eliminated, and enumeration that chooses a variable and a value for this variable to continue the search when no further propagation is possible. Constraint based languages offer a set of static enumeration strategies. The strategy chosen may affect drastically the time required to find a solution. In this paper we propose a framework to model dynamic enumeration strategies using a stochastic, non-deterministic timed concurrent constraint calculus. Thanks to the reactivity of the calculus, we are able to express strategies that dynamically change according to results observed. Additionally, the compositional approach of the calculus enables us to integrate external knowledge to adapt the strategy. In particular, we integrate knowledge from an incomplete solver to guide the enumeration process. Finally, strategies proposed are integrated with a constraint solver to make “good choices” when it explores the search tree allowing to find solutions quicker.
|