Modeling Constrained Combinatorial Problems in Python
Project description
PyCSP3
This is the first (beta) version of PyCSP3, a library in Python for modeling constrained combinatorial problems. PyCSP3 is inspired from both JvCSP3 (a Javabased API) and Numberjack; it is also related to CPpy.
With PyCSP3, it is possible to generate instances of:
 CSPs (Constraint Satisfaction Problems)
 COPs (Constraint Optimization Problems)
in format XCSP3; see www.xcsp.org.
Important: In November 2019, the version 1.0 together with a detailed documentation will be made available on GitHub.
Installation
Installing PyCSP3
For installing PyCSP3, you need to execute:
sudo apt install python3pip
sudo pip3 install pycsp3
Updating PyCSP3
For updating your version of PyCSP3, simply execute:
sudo pip3 install upgrade pycsp3
Compiling PyCSP3 Models
For generating an XCSP3 file from a PyCSP3 model, you have to execute:
python3 <file> [options]
with:
 <file>: a Python file to be executed, describing a model in PyCSP3
 [options]: possible options to be used when compiling
Among the options, we find:

data=<data_value>
: allows us to specify the data to be used by the model. It can be: elementary: data=5
 a simple list: data=[9,0,0,3,9]
 a named list: data=[v=9,b=0,r=0,k=3,l=9]
 a JSON file: data=Bibd346.json
Data can then be directly used in the PyCSP3 model by means of a predefined object
data
. 
dataparser=<file>
: a Python file for reading/parsing data given under any arbitrary form (e.g., by a text file). See Example Nonogram below, for an illustration. 
dataexport
: exports (saves) the data in JSON format. See Example Nonogram below, for an illustration. 
variant=<variant_name>
: the name of a variant, to be used with functionvariant()
. See Example AllInterval below, for an illustration.
Copying a pool of models
PyCSP3 is accompanied by more than 100 models.
To get them in a subdirectory problems
of your current directory, execute:
python3 m pycsp3
Some Examples
We succinctly introduce a few PyCSP3 models, showing how to compile them with different options.
Example 1: in console mode
Our first example shows how you can build basic models in console mode. In this example, we just post two variable and two simple binary constraints.
$ python3
Python 3.5.2
>>> from pycsp3 import *
>>> x = Var(range(10))
>>> y = Var(range(10))
>>> satisfy(
x < y,
x + y > 15
)
>>> compile()
Note that to get an XCSP3 file, we call compile()
.
Example 2: Send+More=Money
This example shows how you can define a model when no data is required from the user. This is the classical cryptoarithmetic puzzle 'Send+More=Money'.
File SendMore.py
from pycsp3 import *
letters = VarArray(size=8, dom=range(10))
s, e, n, d, m, o, r, y = letters
satisfy(
AllDifferent(letters),
s > 0,
m > 0,
[s, e, n, d] * [1000, 100, 10, 1] + [m, o, r, e] * [1000, 100, 10, 1] == [m, o, n, e, y] * [10000, 1000, 100, 10, 1]
)
To generate the XCSP3 instance (file), the command is:
python3 SendMore.py
Example 3: AllInterval Series
This example shows how you can simply specify an integer (as unique data) for a model. For our illustration, we consider the problem AllInterval Series.
A classical model is:
File AllInterval.py
(version 1)
from pycsp3 import *
n = data.n
# x[i] is the ith value of the series
x = VarArray(size=n, dom=range(n))
satisfy(
AllDifferent(x),
AllDifferent(abs(x[i]  x[i + 1]) for i in range(n  1)),
# tag(symmetrybreaking)
x[0] < x[n  1]
)
Note the presence of a tag symmetrybreaking
that will be directly integrated into the XCSP3 file generated by the following command:
python3 AllInterval.py data=5
Suppose that you would prefer to declare a second array of variables for representing successive distances. This would give:
File AllInterval.py
(version 2)
from pycsp3 import *
n = data.n
# x[i] is the ith value of the series
x = VarArray(size=n, dom=range(n))
# y[i] is the distance between x[i] and x[i+1]
y = VarArray(size=n  1, dom=range(1, n))
satisfy(
AllDifferent(x),
AllDifferent(y),
[y[i] == abs(x[i]  x[i + 1]) for i in range(n  1)],
# tag(symmetrybreaking)
[x[0] < x[n  1], y[0] < y[1]]
)
However, sometimes, it may be relevant to combine different variants of a model in the same file. In our example, this would give:
File AllInterval.py
(version 3)
from pycsp3 import *
n = data.n
# x[i] is the ith value of the series
x = VarArray(size=n, dom=range(n))
if not variant():
satisfy(
AllDifferent(x),
AllDifferent(abs(x[i]  x[i + 1]) for i in range(n  1)),
# tag(symmetrybreaking)
x[0] < x[n  1]
)
elif variant("aux"):
# y[i] is the distance between x[i] and x[i+1]
y = VarArray(size=n  1, dom=range(1, n))
satisfy(
AllDifferent(x),
AllDifferent(y),
[y[i] == abs(x[i]  x[i + 1]) for i in range(n  1)],
# tag(symmetrybreaking)
[x[0] < x[n  1], y[0] < y[1]]
)
For compiling the main model (variant), the command is:
python3 AllInterval.py data=5
For compiling the second model variant, using the option variant
, the command is:
python3 AllInterval.py data=5 variant=aux
Example 4: BIBD
This example shows how you can specify a list of integers to be used as data for a model.
For our illustration, we consider the problem BIBD.
We need five integers v, b, r, k, l
for specifying a unique instance (possibly, b
and r
can be set to 0, so that these values are automatically computed according to a template for this problem).
The model is:
File Bibd.py
from pycsp3 import *
v, b, r, k, l = data.v, data.b, data.r, data.k, data.l
b = (l * v * (v  1)) // (k * (k  1)) if b == 0 else b
r = (l * (v  1)) // (k  1) if r == 0 else r
# x[i][j] is the value of the matrix at row i and column j
x = VarArray(size=[v, b], dom={0, 1})
satisfy(
# constraints on rows
[Sum(row) == r for row in x],
# constraints on columns
[Sum(col) == k for col in columns(x)],
# scalar constraints with respect to lambda
[row1 * row2 == l for (row1, row2) in combinations(x, 2)]
)
To generate an XCSP3 instance (file), we can for example execute a command like:
python3 Bibd.py data=[9,0,0,3,9]
Certainly, you wonder how values are associated with fields of data
.
Actually, the order of occurrences of these fields in the model is automatically used.
The first occurrence of a field of data
is data.v
, then it is data.b
, and so on.
So, we have data.v=9
, data.b=0
, ...
However, you can relax this requirement by using names when specifying data, as for example, in:
python3 Bibd.py data=[k=3,l=9,b=0,r=0,v=9]
Example 5: Rack Configuration
This example shows how you can specify a JSON file to be used as data for a model. For our illustration, we consider the problem Rack Configuration. The data (for a specific instance) are then initially given in a JSON file, as for example:
File Rack_r2.json
{
"nRacks": 10,
"models": [[150,8,150],[200,16,200]],
"cardTypes": [[20,20],[40,8],[50,4],[75,2]]
}
In the following model, we directly use the object data
whose fields are exactly those of the main object in the JSON file.
File Rack.py
from pycsp3 import *
nRacks, models, cardTypes = data.nRacks, data.models, data.cardTypes
# we add first a dummy model (0,0,0)
models = [(0, 0, 0)] + [tuple(model) for model in models]
nModels, nTypes = len(models), len(cardTypes)
powers, connectors, prices = [row[0] for row in models], [row[1] for row in models], [row[2] for row in models]
cardPowers = [row[0] for row in cardTypes]
maxCapacity = max(connectors)
# r[i] is the model used for the ith rack
r = VarArray(size=nRacks, dom=range(nModels))
# c[i][j] is the number of cards of type j put in the ith rack
c = VarArray(size=[nRacks, nTypes], dom=lambda i, j: range(min(maxCapacity, cardTypes[j][1]) + 1))
# rpw[i] is the power of the ith rack
rpw = VarArray(size=nRacks, dom=set(powers))
# rcn[i] is the number of connectors of the ith rack
rcn = VarArray(size=nRacks, dom=set(connectors))
# rpr[i] is the price of the ith rack
rpr = VarArray(size=nRacks, dom=set(prices))
satisfy(
# linking the ith rack with its power
[(r[i], rpw[i]) in enumerate(powers) for i in range(nRacks)],
# linking the ith rack with its number of connectors
[(r[i], rcn[i]) in enumerate(connectors) for i in range(nRacks)],
# linking the ith rack with its price
[(r[i], rpr[i]) in enumerate(prices) for i in range(nRacks)],
# connectorcapacity constraints
[Sum(c[i]) <= rcn[i] for i in range(nRacks)],
# powercapacity constraints
[Sum(c[i] * cardPowers) <= rpw[i] for i in range(nRacks)],
# demand constraints
[Sum(c[:, i]) == cardTypes[i][1] for i in range(nTypes)],
# tag(symmetrybreaking)
[
Decreasing(r),
(r[0] != r[1])  (c[0][0] >= c[1][0])
]
)
minimize(
Sum(rpr)
)
To generate an XCSP3 instance (file), we execute the command:
python3 Rack.py data=Rack_r2.json
It is important to note that data in JSON can be arbitrarily structured, as for example:
File Rack_r2b.json
{
"nRacks": 10,
"rackModels": [
{"power":150,"nConnectors":8,"price":150},
{"power":200,"nConnectors":16,"price":200}
],
"cardTypes": [
{"power":20,"demand":20},
{"power":40,"demand":8},
{"power":50,"demand":4},
{"power":75,"demand":2}
]
}
The following model uses this new structure of data.
File Rack2.py
from pycsp3 import *
nRacks, models, cardTypes = data.nRacks, data.rackModels, data.cardTypes
# we add first a dummy model (0,0,0)
models = [{'power': 0, 'nConnectors': 0, 'price': 0}] + models
nModels, nTypes = len(models), len(cardTypes)
powers, connectors, prices = [model['power'] for model in models], [model['nConnectors'] for model in models], [model['price'] for model in models]
cardPowers = [cardType['power'] for cardType in cardTypes]
maxCapacity = max(connectors)
# r[i] is the model used for the ith rack
r = VarArray(size=nRacks, dom=range(nModels))
# c[i][j] is the number of cards of type j put in the ith rack
c = VarArray(size=[nRacks, nTypes], dom=lambda i, j: range(min(maxCapacity, cardTypes[j]['demand'])+1))
# rpw[i] is the power of the ith rack
rpw = VarArray(size=nRacks, dom=set(powers))
# rcn[i] is the number of connectors of the ith rack
rcn = VarArray(size=nRacks, dom=set(connectors))
# rpr[i] is the price of the ith rack
rpr = VarArray(size=nRacks, dom=set(prices))
satisfy(
# linking the ith rack with its power
[(r[i], rpw[i]) in enumerate(powers) for i in range(nRacks)],
# linking the ith rack with its number of connectors
[(r[i], rcn[i]) in enumerate(connectors) for i in range(nRacks)],
# linking the ith rack with its price
[(r[i], rpr[i]) in enumerate(prices) for i in range(nRacks)],
# connectorcapacity constraints
[Sum(c[i]) <= rcn[i] for i in range(nRacks)],
# powercapacity constraints
[Sum(c[i] * cardPowers) <= rpw[i] for i in range(nRacks)],
# demand constraints
[Sum(c[:, i]) == cardTypes[i]['demand'] for i in range(nTypes)],
# tag(symmetrybreaking)
[
Decreasing(r),
(r[0] != r[1])  (c[0][0] >= c[1][0])
]
)
minimize(
Sum(rpr)
)
To generate an XCSP3 instance (file), we execute the command:
python3 Rack2.py data=Rack_r2b.json
Example 6: Nonogram
This example shows how you can use an auxiliary Python file for parsing data that are not initially given under JSON format. For our illustration, we consider the problem Nonogram. The data (for a specific Nonogram puzzle) are initially given in a text file as follows:
 a line stating the numbers of rows and columns,
 then, for each row a line stating the number of blocks followed by the sizes of all these blocks (on the same line),
 then, for each column a line stating the number of blocks followed by the sizes of all these blocks (on the same line).
Below, here is an example of such a text file.
File Nonogram_example.txt
24 24
0
1 5
2 3 3
2 1 2
2 2 1
2 1 1
2 3 3
3 1 5 1
3 1 1 1
3 2 1 1
3 1 1 2
3 3 1 3
3 1 3 1
3 1 1 1
3 2 1 2
3 1 1 1
1 5
3 1 1 1
3 1 1 1
3 1 1 1
3 5 1 1
2 1 2
3 2 2 4
2 4 9
0
0
0
1 1
1 2
1 2
2 6 1
3 3 1 3
3 1 1 4
4 2 1 1 7
5 1 1 1 1 1
3 1 12 1
5 1 1 1 1 1
4 2 1 1 7
4 1 1 4 1
4 2 1 2 2
2 8 3
2 1 1
2 1 2
1 4
1 3
1 2
1 1
0
First, we need to write a piece of code in Python for building an object data
that will be directly used in our model.
We have first to import everything (*) from pycsp3.problems.data.dataparser
.
We can then add any new arbitrary field to the object data
.
This is what we do below with two fields called rowPatterns
and colPatterns
.
These two fields are defined as twodimensional arrays (lists) of integers, defining the sizes of blocks.
The function next_int()
can be called for reading the next integer in a text file, which will be specified on the command line (see later).
File Nonogram_Parser.py
from pycsp3.problems.data.dataparser import *
nRows, nCols = next_int(), next_int()
data.rowPatterns = [[next_int() for _ in range(next_int())] for _ in range(nRows)]
data.colPatterns = [[next_int() for _ in range(next_int())] for _ in range(nRows)]
Then, we just write the model by getting data from the object data
.
The model is totally independent of the way data were initially given (from a text file or a JSON file, for example).
In the code below, note how an object Automaton
is defined from a specified pattern (list of blocks).
Also, for a regular
constraint, we just write something like scope in automaton
.
Finally, x[:, j]
denotes the jth column of x
.
File Nonogram.py
from pycsp3 import *
def automaton(pattern):
def q(i):
return "q" + str(i)
transitions = []
if len(pattern) == 0:
n_states = 1
transitions.append((q(0), 0, q(0)))
else:
n_states = sum(pattern) + len(pattern)
num = 0
for i in range(len(pattern)):
transitions.append((q(num), 0, q(num)))
for j in range(pattern[i]):
transitions.append((q(num), 1, q(num + 1)))
num += 1
if i < len(pattern)  1:
transitions.append((q(num), 0, q(num + 1)))
num += 1
transitions.append((q(num), 0, q(num)))
return Automaton(start=q(0), final=q(n_states  1), transitions=transitions)
rows, cols = data.rowPatterns, data.colPatterns
nRows, nCols = len(rows), len(cols)
# x[i][j] is 1 iff the cell at row i and col j is colored in black
x = VarArray(size=[nRows, nCols], dom={0, 1})
satisfy(
[x[i] in automaton(rows[i]) for i in range(nRows)],
[x[:, j] in automaton(cols[j]) for j in range(nCols)]
)
To generate the XCSP3 instance (file), we just need to specify the name of the text file (option data
) and the name of the Python parser (option dataparser
).
python3 Nonogram.py data=Nonogram_example.txt dataparser=Nonogram_Parser.py
Maybe, you think that it would be simpler to have directly the data in JSON file.
You can generate such a file with the option dataexport
.
The command is as follows:
python3 Nonogram.py data=Nonogram_example.txt dataparser=Nonogram_Parser.py dataexport
A file Nonogram_example.json
is generated, whose content is:
{
"colPatterns":[[],[],[],[1],[2],[2],[6,1],[3,1,3],[1,1,4],[2,1,1,7],[1,1,1,1,1],[1,12,1],[1,1,1,1,1],[2,1,1,7],[1,1,4,1],[2,1,2,2],[8,3],[1,1],[1,2],[4],[3],[2],[1],[]],
"rowPatterns":[[],[5],[3,3],[1,2],[2,1],[1,1],[3,3],[1,5,1],[1,1,1],[2,1,1],[1,1,2],[3,1,3],[1,3,1],[1,1,1],[2,1,2],[1,1,1],[5],[1,1,1],[1,1,1],[1,1,1],[5,1,1],[1,2],[2,2,4],[4,9]]
}
With this new file, you can directly generate the XCSP3 file with:
python3 Nonogram.py data=Nonogram_example.json
Project details
Release history Release notifications  RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.