Constraint Intension

A constraint Intension corresponds to a Boolean expression that may involve variables, constants and various (arithmetic, relational and logical) operators. For example, the constraint $x+y = z$ corresponds to an equation, which is an expression evaluated to false or true according to the values assigned to the variables $x$, $y$ and $z$.

Remark. Note that for equality, we need to use ‘==’ in Python (the operator ‘=’ used for assignment cannot be redefined), and so, the previous constraint must be written $x+y == z$ in PyCSP$^3$.

Remark. Note that the integer values $0$ and $1$ are respectively equivalent to the Boolean values false and true. This allows us to combine Boolean expressions with arithmetic operators (for example, addition) without requiring any type conversions. For example, it is valid to write $(x < 5) + (y < z) == 1$ for stating that exactly one of the Boolean expressions $x<5$ and $y<z$ must be true, although it may be possible (and/or relevant) to write it differently.

To build predicates, classical arithmetic, relational and logical operators (and functions) are available; they are presented in the following tables.

Below, we give several illustrations corresponding to representative use cases of the constraint Intension.

Case 1: Simple Arithmetic Constraint

The first case is a constraint Intension that corersponds to a simple arithmetic constraint.

To see how this constraint works, we need first to import the library PyCSP$^3$:

from pycsp3 import *

For our illustration, we introduce two stand-alone variables $x$ and $y$, each one with $0..9$ as domain

x = Var(range(10))
y = Var(range(10))

We simply post a single constraint Intension imposing that the sum of the values assigned to the variables $x$ and $y$ is strictly less than 10.

satisfy(
    x + y < 10
);

We can display the internal representation of the posted constraint; although a little bit technical, we can see that the constraint is correctly recorded (note that ‘lt’ stands for ‘(strictly) less than’).

print(posted())

intension(function:lt(add(x,y),10))

By calling the function solve(), we can check that the problem (actually, the single constraint) is satisfiable (SAT). We can also print the values assigned to the variables in the found solution by calling the function value().

if solve() is SAT:
    print("Values of x and y: ", value(x), value(y))

Values of x and y:  0 0

On can anticipate that the number of solutions (supports) for this constraint is $\sum_{i=1}^{10} i = 55$

if solve(sols=ALL) is SAT:
    print("Number of solutions: ", n_solutions())

Number of solutions:  55

Case 2: Another Arithmetic Constraint

To test another constraint, we remove the one that has just been posted by calling the function unpost().

unpost()

We control that there are no more constraints.

print(posted())

[]

We now post a single constraint Intension imposing that the distance between the values assigned to the variables $x$ and $y$ is strictly less than 10.

satisfy(
    abs(x - y) >= 7
);

We can enumerate all solutions (supports) of this constraint as follows:

if solve(sols=ALL) is SAT:
    for i in range(n_solutions()):
        print(f"Solution {i+1}: {value(x, sol=i)} {value(y, sol=i)}")

Solution 1: 0 7
Solution 2: 0 8
Solution 3: 0 9
Solution 4: 1 9
Solution 5: 2 9
Solution 6: 7 0
Solution 7: 8 0
Solution 8: 9 0
Solution 9: 9 1
Solution 10: 8 1
Solution 11: 9 2
Solution 12: 1 8

Case 3: A Logical Combination

The third case is about a constraint Intension involving a logical operator.

First, we need to remove the one that has just been posted by calling the function unpost().

unpost()

We now post a single constraint Intension imposing that either the value assigned to $x$ is strictly less than 2 or the value assigned to $y$ is equal to 4.

If we post this inadequate form of constraint Intension, we obtain a warning.

satisfy(
    x < 2 or y == 4
);

  Warning: A node is evaluated as a Boolean (technically, __bool__ is called).
	It is likely a problem with the use of logical operators.
	For example, you must write (x[0] == x[1])  | (x[0] == x[2]) instead of (x[0] == x[1])  or (x[0] == x[2])
	It is also possible that you write: If(cond, Then=...) while cond being not constraint-based
	  that is, not involving a variable of the model; and this is not possible.
	See also the end of section about constraint Intension in chapter 'Twenty popular constraints' of the guide.
	This is: lt(x,2)

By displaying the internal representation of the constraint, one can clearly see that there is a problem.

print(posted())

intension(function:lt(x,2))

The problem is that we cannot use the keywords or, and and not, when writing constraints Intension. This is because we cannot redefine these keywords. Instead, we have to use the operators |, & and ~.

Let us discard this flawed expression.

unpost()

Imagine now that we write the expression as follows:

satisfy(
    x < 2 | y == 4
);

An error occurs because an int and a Variable cannot be combined by the operator |.

And if we try this equivalent expression, we obtain a warning.

satisfy(
    2 > x | y == 4
);

  Warning: A node is evaluated as a Boolean (technically, __bool__ is called).
	It is likely a problem with the use of logical operators.
	For example, you must write (x[0] == x[1])  | (x[0] == x[2]) instead of (x[0] == x[1])  or (x[0] == x[2])
	It is also possible that you write: If(cond, Then=...) while cond being not constraint-based
	  that is, not involving a variable of the model; and this is not possible.
	See also the end of section about constraint Intension in chapter 'Twenty popular constraints' of the guide.
	This is: lt(or(x,y),2)

By displaying the internal representation of the constraint, one can clearly see that there is again a problem.

print(posted())

intension(function:eq(or(x,y),4))

The problem is that we need to surround subexpressions with brackets.

Let us discard this flawed expression.

unpost()

And, now let us write:

satisfy(
    (x < 2) | (y == 4)
);

Let us print the posted constraint, to control it.

print(posted())

intension(function:or(lt(x,2),eq(y,4)))

That looks correct. So let us run the solver:

if solve() is SAT:
    print("Values of x and y: ", value(x), value(y))

Values of x and y:  0 0

To be convinced that everything is ok, let us enumerate all solutions.

if solve(sols=ALL) is SAT:
    for i in range(n_solutions()):
        print(f"Solution {i+1}: {value(x, sol=i)} {value(y, sol=i)}")

Solution 1: 0 0
Solution 2: 0 1
Solution 3: 0 2
Solution 4: 0 3
Solution 5: 0 4
Solution 6: 0 5
Solution 7: 0 6
Solution 8: 0 7
Solution 9: 0 8
Solution 10: 0 9
Solution 11: 1 9
Solution 12: 1 0
Solution 13: 1 1
Solution 14: 1 2
Solution 15: 1 3
Solution 16: 1 4
Solution 17: 2 4
Solution 18: 3 4
Solution 19: 4 4
Solution 20: 5 4
Solution 21: 6 4
Solution 22: 7 4
Solution 23: 8 4
Solution 24: 9 4
Solution 25: 1 5
Solution 26: 1 6
Solution 27: 1 7
Solution 28: 1 8

Often it is possible to avoid using the logic operators by calling the functions both and either (and the more general functions conjunction and disjunction). For example:

unpost()

satisfy(
    either(x < 2, y == 4)
)

print(posted())

intension(function:or(lt(x,2),eq(y,4)))

Related Models

• Amaze
• BACP
• CommunityDetection
• CryptoPuzzle
• Diagnosis
• FreePizza
• KidneyExchange
• QuasiGroup
• Rack
• RCPSP
• RectanglePacking
• SocialGolfers
• StableMarriage
• Sudoku
• TravelingTournament
• Vellino1