Séminaire APR
[Séminaire APR] Toward more generic and robust constraint solvers
Thursday, February 20, 2020Charlotte Truchet (Université de Nantes)
Constraint Programming (CP) provides tools to model and solve combinatorial problems, expressed declaratively. Efficient dedicated algorithms have been defined for given combinatorial sub-structures (such as cardinality, constraints, geometric properties, etc). These algorithms can be combined inside a generic solving process, making CP a powerful tool to tackle problems from a wide range of applications. Yet, obtaining good performances from a CP solver requires a high level of expertise. Besides, most of the solvers are restricted to a single type of variables (real or integer). These restrictions limit the applications of CP to computer scientists with a good knowledge of the field. In this talk, I will first present some average-case analysis results of CP solver components, meant to better understand their behavior and define solvers which are easier to tune. Then, I will introduce a generic solving process based on abstract domains, as defined in Abstract Interpretation, and show how these domains can both extend the expressivity of CP solvers, and offer a good balance between very specific global constraints, and less efficient generic languages. In particular, I will detail how to dynamically learn constraints inside these CP abstract domains.
romain.demangeon (at) nulllip6.fr