Detail

Publication date: 1 de June, 2021

Modern Techniques for Constraint Solving: The CaSPER experience

Constraint programming is a well known paradigm for addressing combinatorial problems which has enjoyed considerable success for solving many relevant industrial and academic problems. In the heart constraint programming lies the constraint solver, a computer program which attempts to find a solution to the problem, i.e. an assignment of all the variables in the problem such that all the constraints are satisfied.

This presentation describes a set of techniques to be used in the implementation of a constraint solver. These techniques aim at making a constraint solver more extensible and efficient, two properties which are hard to integrate in general, and in particular within a constraint solver. Specifically, we will address two major problems: generic incremental propagation and propagation of arbitrary decomposable constraints. For both problems we present a set of techniques which are novel, correct, and directly concerned with extensibility and efficiency.

All the presented material emerged from our work in designing and implementing a generic constraint solver. The CaSPER (Constraint Solving Platform for Engineering and Research) solver does not only act as a proof-of-concept for the presented techniques, but also serves as the common test platform for the many discussed theoretically models. If time allows, this presentation will also cover the first successful application of the resulting platform for addressing an open research problem, namely finding good heuristics for efficiently directing search towards a solution.

---