Abstract
Among model-based combinatorial solving paradigms, Constraint Programming (CP) took the road less traveled: whereas others such as Integer Programming and SAT express models in a low-level homogeneous form, CP models a problem through high-level primitives, called constraints, that expose much of the combinatorial structure of that problem. These diverse primitives have been identified over time as being complex enough to provide structural insight yet simple enough for some desired computing tasks to remain tractable. The distinctive driving force of CP has been this direct access to structure: it has been key to the design of powerful search-space reduction algorithms and it is increasingly exploited to learn from and to guide search.
In this talk I go beyond the traditional domain filtering task over constraints ("Is there any solution to constraint c in which variable x takes on value d?) and address counting ("How many solutions are there to constraint c?"), weighted counting, and marginal probability mass functions over constraints in CP. I discuss the algorithmic challenges to perform such tasks and describe some of the opportunities given the combinatorial insights they provide.