2.1. Global constraint: what it is, and what it is not

As said in the preface, the term global constraint should be understood as an expressive and concise condition involving a non-fixed number of partially known objects. The ideas conveyed by this informal definition are:

• Context independence points to the fact that the condition may be typically useful in more than one context. Like a word in the context of natural language, a global constraint encapsulates its own concept that is independent from any specific use. Like words, once you have the right concepts, you can directly reason at the appropriate level of abstraction.

• Conciseness means that the condition should be expressible in a compact way, typically by one or two sentences in natural language.In Sections 2.3 and 2.4 we will describe some possible ways of defining concisely the meaning of a significant number of global constraints in a formal way. The condition directly mentions objects that match the right level of abstraction it considers, i.e., when appropriate it does not just refer to a flat list of variables. If necessary, the condition typically involves one or several collections of objects (e.g. tasks), where each object has a number of attributes (e.g., an origin, a duration and an end if we consider tasks). An attribute may correspond either to a constant (i.e., a fixed value), or to a variable.

The second key point conveyed by this informal definition is that, it does not make any assumption about the techniques associated with the potential use of global constraints. Consequently, a global constraint cannot just be reduced to:

1. A concept that is only linked to constraint programming.

2. A function that computes a result from a given set of input arguments.

3. An algorithm that, given a condition on a set of variables, removes some values to enforce that condition.

4. A way to express a condition as a set of clauses or as a set of linear constraints.

We now illustrate through the example of the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint different facets of a global constraint. Given a collection of variables $\langle x_1,x_2,\cdots ,x_n\rangle$, the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$\left(\langle x_1,x_2,\cdots ,x_n\rangle \right)$ constraint forces all variables $x_1,x_2,\cdots ,x_n$ to be assigned distinct values. We successively consider the checker view, the feasibility view, the filtering view, the explanation view, the cost violation view, the reification view, the counting view and the property view.

• 2.1.1. Checker view
• 2.1.2. Feasibility view
• 2.1.3. Filtering view
• 2.1.4. Explanation view
• 2.1.5. Cost violation view
• 2.1.6. Reification view
• 2.1.7. Counting view
• 2.1.8. Property view