Constraint Maximum

The constraint Maximum ensures that the maximal value among those assigned to the variables of a specified list $x$ respects a numerical condition.

In PyCSP$^3$, we must call the function Maximum() that allows us to pass the variables either in sequence (individually) or under the form of a list. The object obtained when calling Maximum() must be restricted by a condition (typically, defined by a relational operator and a limit).

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

Case 1: Maximum Greater Than a Constant

We consider the case where we have a list of variables whose maximum must be greater than a constant.

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

from pycsp3 import *

For our illustration, we introduce an array $x$ of 4 variables, each variable having {0,1,2,3} as domain.

x = VarArray(size=4, dom=range(4))

We can display (the structure of) the array as well as the domain of the first variable.

print("Array of variable x: ", x)
print("Domain of any variable: ", x[0].dom)

Array of variable x:  [x[0], x[1], x[2], x[3]]
Domain of any variable:  0..3

We simply post a single constraint Maximum imposing that the maximal value among those assigned to the variables of $x$ is strictly greater than 1.

satisfy(
    Maximum(x) > 1
);

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; we can call the function values() that collects the values assigned (in the last found solution) to a specified list of variables.

if solve() is SAT:
    print("Values of x: ", values(x))

Values of x:  [0, 0, 0, 2]

On this simple constraint, one can infer that the number of solutions (supports) is 240, out of $4^4 = 256$ possible tuples.

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

Last solution:  [2, 1, 0, 1]
Number of solutions:  240

Case 2: Maximum Equal to a Variable

Now, we consider the case where we have a list of variables whose maximum must be equal to a variable.

First of all, we need to remove everything that has been introduced so far.

clear()  # to clear previously posted variables and constraints

Then, we introduce an array $x$ of 4 variables and a stand-alone variable $y$, each variable having {0,1,2} as domain.

x = VarArray(size=4, dom=range(3))
y = Var(range(3))

We simply post a single constraint Maximum imposing that the maximal value among those assigned to the variables of $x$ is equal to the value assigned to $y$.

satisfy(
    Maximum(x) == y
);

We can run the solver.

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

Values of x:  [0, 0, 0, 0]
Value of y:  0

Note that there are exactly 81 solutions (5-tuples called supports) for this constraint, among the $3^5=243$ possible tuples (corresponding to the Cartesian product of the domains).

if solve(sols=ALL) is SAT:
    print("Last solution: ", values(x), " ", value(y))
    print("Number of solutions: ", n_solutions())

Last solution:  [1, 1, 1, 1]   1
Number of solutions:  81

Let us now arbitrarily set the value of $y$ to 1.

satisfy(
    y == 1
);

We can display all solutions as follows:

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

Solution 1: [0, 0, 0, 1] 1
Solution 2: [0, 0, 1, 1] 1
Solution 3: [0, 0, 1, 0] 1
Solution 4: [0, 1, 1, 0] 1
Solution 5: [0, 1, 0, 0] 1
Solution 6: [0, 1, 0, 1] 1
Solution 7: [0, 1, 1, 1] 1
Solution 8: [1, 1, 1, 1] 1
Solution 9: [1, 1, 1, 0] 1
Solution 10: [1, 1, 0, 0] 1
Solution 11: [1, 1, 0, 1] 1
Solution 12: [1, 0, 0, 1] 1
Solution 13: [1, 0, 0, 0] 1
Solution 14: [1, 0, 1, 0] 1
Solution 15: [1, 0, 1, 1] 1

Although this is not the most efficient way of doing that (at each call to the function solve(), a new instance is generated and the solver is loaded; so, in the future, we plan to be able to let the solver alive), we can also enumerate all solutions (supports) of the constraint as follows:

cnt = 0
while solve(solver=CHOCO) is SAT:
    cnt += 1
    print(f"Solution {cnt}: {values(x)}  {value(y)}")
    satisfy(
        x != values(x)
    )

Solution 1: [0, 0, 0, 1]  1
Solution 2: [1, 0, 0, 0]  1
Solution 3: [1, 0, 0, 1]  1
Solution 4: [0, 1, 0, 0]  1
Solution 5: [0, 1, 0, 1]  1
Solution 6: [1, 1, 0, 0]  1
Solution 7: [1, 1, 0, 1]  1
Solution 8: [0, 0, 1, 0]  1
Solution 9: [0, 1, 1, 0]  1
Solution 10: [0, 0, 1, 1]  1
Solution 11: [0, 1, 1, 1]  1
Solution 12: [1, 0, 1, 0]  1
Solution 13: [1, 1, 1, 0]  1
Solution 14: [1, 0, 1, 1]  1
Solution 15: [1, 1, 1, 1]  1

Case 3: Maximum of Expressions

Finally, we consider the case where we have a list of expressions whose maximum must be greater than a constant.

First of all, we need to remove everything that has been introduced so far.

clear()  # to clear previously posted variables and constraints

Then, we introduce an array $x$ of 4 variables, each variable having {0,1,2,3} as domain.

x = VarArray(size=4, dom=range(4))

We post a single constraint Maximum imposing that the maximal value among the specified expressions is greater than or equal to 3.

satisfy(
    Maximum(x[0]+x[1], x[1]+x[2], x[2]+x[3]) >= 5
);

We can run the solver.

if solve() is SAT:
    print("Values of x: ", values(x))

Values of x:  [0, 0, 2, 3]

Related Models

• OpenStacks