Constraints meet concurrency (Q2442869)

A constraint satisfaction problem (CSP) is expressed by a set of constraints. Each constraint imposes some restrictions on the values that variables can assume in a satisfactory assignment. Variables are associated with domains which can be, for example, Boolean truth values, integer or real numbers. Common constraints are conjunctions of Boolean literals which express invalid assignments to the variables occurring in the conjunction, and inequalities with integer or real coefficients that variable assignments must satisfy. Another common constraint is ``all different'', which essentially requires that all variables in a given set are assigned to different values in their domains. CSP instances are usually solved by backtracking algorithms that have several commonalities with those used to find satisfying assignments for propositional formulas in conjunctive normal form. Some CSP solvers also allow the user to specify custom constraints. In particular, some of them use a declarative programming language known as Constraint Handling Rules (CHR). A CHR program is a set of three kinds of rules, referred to as \textit{simplification}, \textit{propagation} and \textit{simpagation} rules. A simplification rule combines constraints in order to obtain a simpler constraint. A propagation rule, instead, adds constraints that are logically implied by other constraints in the program in order to trigger some simplifications. Finally, a simpagation rule combines the effects of simplification and propagation rules. The semantics of CHR programs is operational: Rules define transitions between valid configurations of the system associated with the program. In this way, CHR is a Turing-complete language. Limitations must be, thus, imposed to the full language in order to regain decidability. In particular, in this book two fragments of CHR are introduced. The first fragment allows only for range-restricted rules, that is, all variables in a rule must also appear in the head. The second fragment instead allows only for rules with atomic heads. A solver for CSP instances that distributes the computation among different nodes in a network is also presented in this book. The idea is to provide an on-demand service to solve problems modeled by constraints. Since it is well known that different CSP solvers are usually better at solving different CSP instances, machine learning techniques are employed to predict the best solvers for the input instances. Instances are then distributed over the network to the nodes providing the right solvers, also taking into account problems of resource balancing. The efficiency of the implemented system is empirically assessed on several benchmarks.