10.9.1 Introduction

The solver described in this chapter is suitable for solving problems modeled as Constraint Satisfaction Problems (CSPs). The components of a CSP are:

variables

The CLPFD solver deals with variables that take integer or real numbers as values. Variables known to the solver are called domain variables.

domains

At any given time, a domain variable has an attached domain, a subset of the integers or the reals. Domains can be declared up front. Such declarations are not always mandatory.

constraints

A constraint is a relation over a set of domain variables. If those variables are all ground, the constraint is false or true. The semantics of a constraint can be defined in a number of ways, but fundamentally can be thought of as the set of value tuples for which the constraint is true.

objective function

A CSP can be a satisfiability problem of an optimization problem. In the latter case, an objective function is needed, whose value is the value to minimize or maximize

search procedure

The goal of any CSP is to find an assignment to all domain variables satisfying all constraints and minimizing or maximizing the objective function, if one was given. Some amount of search is almost always necessary to find such an assignment.

The term finite domains is a legacy term referring to constraints where all domains are finite sets of integers. Earlier versions of the solver did not support real numbers. Domains could always be finite. The Handbook of Constraint Programming [CPHandbook] gives an excellent overview of Constraint Programming with deep dives into the foundations and many lines of work that have been and are being pursued in the field.

The CLPFD solver can be used via the Prolog API described in this chapter, as well as a back-end to the MiniZinc toolchain [MiniZincHandbook] (see lib-zinc).