Link Search Menu Expand Document
PyCSP3
Models & Data GitHub XCSP3 About
Documentation
XCSP web site is provided by CRIL
This site uses Just the Docs, a documentation theme for Jekyll.
download notebook

Module Interface

In this section, we briefly review all components (constants, variables, functions) that are available from the main module of the library PyCSP$^3$. This is what you get when executing:

from pycsp3 import *

In the next sub-sections, we introduce the different categories of such components.

Building Models

The main functions for building CSP and COP models are about:

  • declaring stand-alone variables, and arrays of variables
    • Var()
    • VarArray()
  • posting constraints
    • satisfy()
  • specifying an objective
    • minimize()
    • maximize()
  • managing several model variants
    • variant()
    • subvariant()

How to declare variables is discussed here. How to post constraints is discussed here. How to specify an objective is discussed here. How to manage variants and subvariants is illustrated here.

Building Expressions

When building expressions of intensional constraints, one can use constants, variables, and arithmetic, relational, and logic operators (which are redefined to this particular purpose). In addition to the Python functions:

  • abs()
  • min()
  • max()

which are also extended (redefined), one can use the following specific functions:

  • xor()
  • iff()
  • imply()
  • ift()
  • expr()
  • both()
  • either()
  • conjunction()
  • disjunction()

For example, the 8 constraints of this demonstration model:

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

satisfy(
    xor(x[0] == 0, x[1] == 1, x[2] == 2),
    iff(x[0] < 3, x[1] != 2),
    iff(x[i] != i for i in range(6)),
    imply(x[0] > 2, x[1] == 4),
    ift(x[0] == 1, x[1] == 2, x[2] == 3),
    expr("<", x[0], 4),
    both(x[0] > 0, x[1] < 3),
    either(x[0] > 0, x[1] < 3),
    conjunction(x[i] != i for i in range(6)),
    disjunction(x[i] != i for i in range(6)),
);

correspond to constraints Intension whose expressions in prefix notation are visible when calling posted():

print(posted())

intension(function:xor(eq(x[0],0),eq(x[1],1),eq(x[2],2)))
intension(function:iff(lt(x[0],3),ne(x[1],2)))
intension(function:iff(ne(x[0],0),ne(x[1],1),ne(x[2],2),ne(x[3],3),ne(x[4],4),ne(x[5],5)))
intension(function:imp(gt(x[0],2),eq(x[1],4)))
intension(function:if(eq(x[0],1),eq(x[1],2),eq(x[2],3)))
intension(function:lt(x[0],4))
intension(function:and(gt(x[0],0),lt(x[1],3)))
intension(function:or(gt(x[0],0),lt(x[1],3)))
intension(function:and(ne(x[0],0),ne(x[1],1),ne(x[2],2),ne(x[3],3),ne(x[4],4),ne(x[5],5)))
intension(function:or(ne(x[0],0),ne(x[1],1),ne(x[2],2),ne(x[3],3),ne(x[4],4),ne(x[5],5)))

Although a little bit technical, we can see the correspondances. Note that ‘eq’, ‘ne’, ‘lt’, ‘gt’ stands for ‘equal to’, ‘not equal to’, ‘strictly less than’, ‘strictly greater than’, respectively.

A related function is:

  • protect()

that allows us to execute some piece of code while all redefined operators are temporarily deactivated. To be effective, one must chain the call to protect() with a call to execute() with the piece of code to be executed in protected mode. As an illustration, if we execute:

clear()

x = Var(0,1)
y = Var(0,1)

print(x == y)
print(protect().execute(x == x))
print(protect().execute(x == y))

eq(x,y)
True
False

Building Global Constraints

Some constraints can be built by simply using the (redefined) operators (and functions) of Python. This is mainly the case for constraints Intension, Extension and also Element. For the other global constraints, here is the list of functions to be called:

  • Automaton() and MDD()
  • AllDifferent(), AllDifferentList(), AllEqual()
  • Increasing(), Decreasing(), LexIncreasing(), LexDecreasing(), Precedence()
  • Sum(), Count(), NValues(), Cardinality()
  • Maximum(), Minimum(), MaximumArg(), MinimumArg(), Channel()
  • NoOverlap(), Cumulative(), BinPacking(), Knapsack()
  • Circuit(), Clause()

Details about these functions can be found in the docstrings and in other webpages of this site.

Notice that, as derivated constraint forms, you can find Hamming(), derivated from Sum, as well as Exist(), NotExist(), ExactlyOne(), AtLeastOne(), AtMostOne() and AllHold(), derivated from Count. See Sections 3.11 and 3.12 of the guide.

Loading (Default) JSON Data

Two useful functions to load some JSON data by default, or independently of the main object data are:

  • default_data()
  • loading_json_data()

These functions are described here.

Handling Lists (Matrices)

Rather often, we need to handle matrices (i.e., two-dimensional lists) of integers or variables. The following functions can be helpful:

  • columns()
  • diagonal_down()
  • diagonals_down()
  • diagonal_up()
  • diagonals_up()

The function columns() actually computes a transpose matrix. Let us illustrate it with:

clear()

x = VarArray(size=[3,4], dom={0,1})

print(x)
print(columns(x))

[
  [x[0][0], x[0][1], x[0][2], x[0][3]]
  [x[1][0], x[1][1], x[1][2], x[1][3]]
  [x[2][0], x[2][1], x[2][2], x[2][3]]
]
[
  [x[0][0], x[1][0], x[2][0]]
  [x[0][1], x[1][1], x[2][1]]
  [x[0][2], x[1][2], x[2][2]]
  [x[0][3], x[1][3], x[2][3]]
]

As an illustration of functions that are useful for extracting diagonals, let us execute:

y = VarArray(size=[4,4], dom={0,1})

print(diagonal_down(y))
print(diagonals_down(y))
print(diagonals_down(y, broken=True))

[y[0][0], y[1][1], y[2][2], y[3][3]]
[
  [y[2][0], y[3][1]]
  [y[1][0], y[2][1], y[3][2]]
  [y[0][0], y[1][1], y[2][2], y[3][3]]
  [y[0][1], y[1][2], y[2][3]]
  [y[0][2], y[1][3]]
]
[
  [y[0][0], y[1][1], y[2][2], y[3][3]]
  [y[0][3], y[1][0], y[2][1], y[3][2]]
  [y[0][2], y[1][3], y[2][0], y[3][1]]
  [y[0][1], y[1][2], y[2][3], y[3][0]]
]

Finally, the function cp_array() allows us to transform any list (of any dimension) of integers into a more specific type called ‘ListInt’ that inherits from list. Similarly, it allows us to transform any list (of any dimension) of variables into a more specific type called ‘ListVar’ that inherits from list. It is important to have such specific types of lists when using the constraint Element. Importantly, when the data are loaded from a file (the usual case), all lists of integers have the specific type of list returned by cp_array(), and so, it is very rare to need to call this function explicitly.

Here is an illustration:

t = [3, 4, 5]
print(type(t))
t = cp_array(t)
print(type(t))

<class 'list'>
<class 'pycsp3.tools.curser.ListInt'>

Another illustration is:

z = VarArray(size=5, dom={0,1})

print(type(z))
zz = [z[0], z[2], z[4]]
print(type(zz))
zz = cp_array(zz)
print(type(zz))

<class 'pycsp3.tools.curser.ListVar'>
<class 'list'>
<class 'pycsp3.tools.curser.ListVar'>

Let us reacll that when a list is from type ‘ListVar’ or ‘ListInt’, it can be used in the expression of a constraint Element.

Handling Tuples

From package itertools, the following functions are directly available:

  • product()
  • permutations()
  • combinations()

Note that the function combinations() is slightly extended so as to permit the first argument to be an integer. In that case, this value is converted into a range. For example, if we execute:

print([tuple for tuple in combinations(5,2)])

[(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

Utility Computations

Some utility functions are:

  • different_values()
  • flatten()
  • alphabet_positions()
  • all_primes()
  • integer_scaling()

The function different_values() just checks that all specified arguments are different. The function flatten() builds a one-dimensional list with all elements that can be encountered when looking into the specified arguments (typically, this is a list of possibly any dimension). None values are discarded except if the optional named parameter keep_none is set to True. For example, if we execute:

clear()

x = VarArray(size=[3,3], dom=lambda i,j: {0,1} if i >= j else None)
print("x: ", x)
print("x flattened: ", flatten(x))

x:  [
  [x[0][0], None, None]
  [x[1][0], x[1][1], None]
  [x[2][0], x[2][1], x[2][2]]
]
x flattened:  [x[0][0], x[1][0], x[1][1], x[2][0], x[2][1], x[2][2]]

The function alphabet_positions() returns a list with the indexes of the letters (with respect to the 26 letters of the Latin alphabet) of a specified string. The function all_primes() returns a list with all prime numbers that are strictly less than the specified limit. The function integer_scaling() returns a list with all specified values after possibly converting them (when decimal) into integers by means of automatic scaling. For example, if we execute:

t = [3, 2.11, 0.0141]
print("t scaled: ", integer_scaling(t))

t scaled:  [30000, 21100, 141]

Building Hybrid Tables

On the one hand, it is rather easy to build starred tuples, which are tuples involving ‘*’, denoted by the constant ANY in PySCP$^3$. Illustrations are given by the models of problems TravelingTournament and Layout.

On the other hand, when creating tables to be used with extensional constraints, one can use some auxiliary functions that capture some patterns (conditions) that can be put at some places inside tuples. Tables are then said to be hybrid. This is presented as Case 4 of constraint Extension. The interest is that it is usually easier (quicker) to build hybrid tables, which are in compressed forms (possibly requiring far less memory space). Besides, we can decide or not to generate such compressed tables when compiling.

For example, assuming that the possible values to work with are {0,1,2,3,4}, the hybrid tuple (0,lt(3),2) represents the set of tuples {(0,0,2),(0,1,2),(0,2,2)} since lt(3) means any value that is strictly less than 3. As a more concrete illustration, let us consider the following demonstration model:

clear()

table = [(0, ANY, gt(1)), (ne(0),(2,3),complement(2,3))]

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

satisfy(
    x in table
);

The constraint expresses the fact that x[0] can be 0 if x[2] > 1, or different from 0 if x[1] in {2,3} and x[2] in {0,1} (the complement of {2,3}). When looking at the outcome of default compilation (the XCSP$^3$ file), one can see that a starred table has been generated. Indeed, by default, hybrid tables are automatically transformed into ordinary/starred tables when compiling. To generate hybrid tables in XCSP$^3$, one has to use the option -keephybrid as shown in Case 4 of constraint Extension.

More specifically, when we build tables, we can use a compressed expression at any place inside a tuple by using one of the following structures or functions:

  • {$v_1, v_2, \dots, v_k$} or ($v_1, v_2, \dots, v_k$) corresponds to any value in the specified set or tuple
  • range(a, b) corresponds to any value in the specified range
  • complement($v_1, v_2, \dots, v_k$) corresponds to any unspecified value
  • complement(range(a, b)) corresponds to any value not present in the specified range
  • $op(v)$ with $op$ being a relational operator in ${ne, lt, le, gt, ge}$ so that:
    • $ne(v)$ corresponds to any value ‘not equal’ to $v$
    • $lt(v)$ corresponds to any value strictly ‘less than’ $v$
    • $le(v)$ corresponds to any value ‘less than or equal to’ $v$
    • $gt(v)$ corresponds to any value strictly ‘greater than’ $v$
    • $ge(v)$ corresponds to any value ‘greater than or equal to’ $v$
  • $op(col(i))$ with op being a relational operator in ${eq, ne, lt, le, gt, ge}$ and $col(i)$ denoting the ‘column’ of the tuple at index $i$, so that:
    • $eq(col(i))$ corresponds to the value at index $i$ in the tuple
    • $ne(col(i))$ corresponds to any value ‘not equal’ to the value at index $i$
    • $lt(col(i))$ corresponds to any value strictly ‘less than’ the value at index $i$
    • $le(col(i))$ corresponds to any value ‘less than or equal to’ the value at index $i$
    • $gt(col(i))$ corresponds to any value strictly ‘greater than’ the value at index $i$
    • $ge(col(i))$ corresponds to any value ‘greater than or equal to’ the value at index $i$
  • $op(col(i) + v)$, defined similarly as above, with $v$ added to the value at index $i$
  • $op(col(i) - v)$, defined similarly as above, with $v$ subtracted to the value at index $i$
  • $op(col(i) + col(j))$, defined similarly as above, with the values at index $i$ and $j$ being added

Hybrid tables are kept when the compilation option -keephybrid is enabled when compiling. Here, in this notebook, this is equivalent to execute:

from pycsp3.dashboard import options
options.keephybrid = True

For this model:

clear()

x = VarArray(size=3, dom=range(10))

table = {
  (range(4, 7), gt(7), ANY),
  (lt(3), ANY, ge(6)),
  (9, ne(2), ANY),
  ((3, 8), ANY, (6, 8)),
  (7, complement(range(2, 8)), complement(1, 3, 5, 7, 9))
}

satisfy(
    x in table
);

we obtain:

print(posted())

extension[TYPE: hybrid-1](list:[x[0], x[1], x[2]], supports:(4..6,≥8,*)(≤2,*,≥6)(7,∁2..7,∁{1,3,5,7,9})(9,≠2,*)({3,8},*,{6,8}))

Although the transformation from hybrid tables to ordinary/starred tables is automatic when compiling (but not the case, with the option -keephybrid, as we have just seen), one may want, for some reasons, to apply explicitly the transformation with the function to_ordinary_table(). This function converts a specified table that may contain hybrid restrictions and stars into an ordinary table (or a starred table). The first argument of the function is a table that contains r-tuples. For converting, the domain to be considered are any index i of these tuples is given by domains[i] where domains is the second argument of the function. In case, domains[i] is an integer, it is automatically transformed into a range. An optional named parameter starred allows us to choose between an ordinary and a starred table. For example:

table = [(0, ANY, gt(1)), (ne(0),(2,3),complement(2,3))]
print("Hybrid table: ", table)
print("Starred Table: ", sorted(to_ordinary_table(table,[4,4,4], possibly_starred=True)))
print("Ordinary Table: ", sorted(to_ordinary_table(table,[4,4,4])))

Hybrid table:  [(0, *, ≥2), (≠0, (2, 3), ∁{2,3})]
Starred Table:  [(0, *, 2), (0, *, 3), (1, 2, 0), (1, 2, 1), (1, 3, 0), (1, 3, 1), (2, 2, 0), (2, 2, 1), (2, 3, 0), (2, 3, 1), (3, 2, 0), (3, 2, 1), (3, 3, 0), (3, 3, 1)]
Ordinary Table:  [(0, 0, 2), (0, 0, 3), (0, 1, 2), (0, 1, 3), (0, 2, 2), (0, 2, 3), (0, 3, 2), (0, 3, 3), (1, 2, 0), (1, 2, 1), (1, 3, 0), (1, 3, 1), (2, 2, 0), (2, 2, 1), (2, 3, 0), (2, 3, 1), (3, 2, 0), (3, 2, 1), (3, 3, 0), (3, 3, 1)]

Building Meta-constraints

It is possible to build meta-constraints by using the following functions:

  • And()
  • Or()
  • Not()
  • Xor()
  • If(), , but requires to set the parameter meta to True
  • Iff()

It is important to note that the first letter of these function names is uppercase. Some illustrations and details are given in this part. For the moment, note that meta-constraints should be avoided as they are not in the perimeter of XCSP$^3$-core.

Solving

Some constants are available. Some concern the result of a solving process, when solve() is called.

  • UNSAT, unsatisfiable (means that no solution is found by the solver)
  • SAT, satisfiable (means that at least one solution is found by the solver)
  • OPTIMUM, optimum (means that an optimal solution is found by the solver)
  • UNKNOWN, unknown (means that the solver is unable to solve the problem instance)
  • CORE, core (means that an unsatisfiable core has been extracted by the solver)

Some concern the choice of a solver:

  • ACE, Solver ACE (AbsCon Essence)
  • CHOCO, Solver Choco

A last constant is

  • ALL, meaning that all solutions must be sought, when used with the parameter sols of solve().

The functions that directly concern the solving process are:

  • solve(): runs the solver on the current instance
  • solver(): returns the current solver, when no argument is given, or sets the current solver with an argument set to the constant ACE or the constant CHOCO
  • status(): returns the result of the last solving process (last call to \nn{solve()})
  • solution(): returns an object with various information (fields) concerning the last found solution
  • value(): returns the value assigned to the variable specified as parameter
  • values(): returns the list of values assigned to the (list of) variables specified as parameter
  • n_solutions(): returns the number of found solutions
  • bound(): returns the value of the objective function corresponding to the last found solution
  • core(): returns the core identified by the last extraction operation

These functions are described and/or illustrated in this part.

Finally, some functions allow us to display the posted constraints (or objective), to remove some posted constraints and to clear everything (variables, constraints, objective):

  • posted(): displays the posted constraints
  • objective(): displays the current objective
  • unpost(): removes the constraints posted by the last call to satisfy().
  • clear(): clears everything (variables, constraints, objective)

These functions are described and/or illustrated in this part.