Séminaire APR


[Séminaire APR] Toward more generic and robust constraint solvers

Thursday, February 20, 2020
Speaker(s) : Charlotte 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