Exploring Process Calculi as a Mechanism to Define Dynamic
Enumeration Strategies in Constraint Programming
 

Eric Monfroy 1, Carlos Olarte 2 and Camilo Rueda 2
1 Universidad Técnica Federico Santa María, Valparaíso, Chile
2 Pontificia Universidad Javeriana, Cali, Colombia
eric.monfroy@univ-nantes.fr, {caolarte,crueda}@atlas.puj.edu.co

 
Abstract
 
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.
 
Keywords:sntcc , Constraint programming, Dynamic enumeration strategies
Resumen
 
La programación por restricciones ha sido utilizada para resolver una gran cantidad de problemas. Su modelo declarativo permite fijar condiciones sobre las variables y un solver genérico encuentra de manera automática una solución. El proceso de calcular una solución en este paradigma consiste en dos fases básicas: Propagación en la que los valores inconsistentes son eliminados del dominio de las variables y enumeración en la que se escoge una variable y un valor para ella y así continuar el proceso cuando no es posible eliminar mas valores del dominio. Los lenguajes basados en este paradigma ofrecen una serie de estrategias estáticas de enumeración. Sin embargo el uso de una estrategia afecta considerablemente el tiempo requerido para encontrar una solución. En este artículo proponemos un framework basado en un cálculo estocástico, no determinístico, concurrente por restricciones para modelar estrategias dinámicas de enumeración. Gracias a que el cálculo es reactivo, las estrategias son capaces de adaptarse de acuerdo a los resultados obtenidos en el proceso de solución. Adicionalmente, gracias al operador de composición paralela, podemos adicionar nueva información del entorno para guiar de mejor manera la búsqueda.
 
Palabras Clave: sntcc , Programacion por Restricciones, Estrategias Dinamicas de enumeracion