Cheat Sheet
Many succinct illustrative examples about how to specify data, declare variables, post constraints and specify an objective.
1) Specifying Data
python Queens.py -data=8 # a single elementary value (integer)
python BIBD.py -data=[9,0,0,3,9] # a list of elementary values
python BIBD.py -data=[v=9,b=0,r=0,k=3,l=9] # a list of named elementary values
python Sudoku.py -data=puzzle.txt -parser=ParserSudoku.py # a text file (needs a parser)
python Sudoku.py -data=puzzle.json # a JSON file
python Sudoku.py -data=https://raw.mysite.com/puzzle.json # a JSON file from an URL
python Test.py -data=[file1.json,file2.json] # several JSON files
python Test.py -data=[file1.json,file2.json,c=5] # with an additional field
python Test2.py -data=[file1.txt,file2.txt] -parser=Parser2.py # several text files
python Test2.py -data=[file1.txt,file2.txt,10] -parser=Parser2.py # with an additional line
2) Declaring Variables
# single variables
v = Var(dom=range(15)) # a variable with domain {0, 1,..., 14}
b = Var(0, 1) # a 0/1 variable (can be seen as a Boolean variable)
v = Var(dom=(0, 2, 4, 6, 8)) # a variable with domain {0, 2, 4, 6, 8}
v = Var(dom={"a", "b", "c"}) # a Variable with symbolic domain {a, b, c}
# arrays of variables
x = VarArray(size=10, dom={0, 1}) # a 1-dimensional array of 0/1 variables
m = VarArray(size=[5, 5], dom=range(10)) # a 2-dimensional array of variables with domain {0, 1,... ,9}
c = VarArray(size=[4, 3, 4], dom={1, 5, 10, 20}) # a 3-dimensional array of variables
# arrays of variables with different domains
m = VarArray(size=[5, 5], dom=lambda i,j: range(5) if j == 0 else range(10))
print(m[:,j]) # print the jth column of m (indexing as in NumPy)
print(m[0:3,0:3]) # print a block of m (indexing as in NumPy)
3) Posting constraints
satisfy(
AllDifferent(x) # a single constraint
)
satisfy(
x[i] < 10 for i in range(n) # a group (generator) of constraints
)
satisfy(
AllDifferent(x), # a first constraint
[x[i] < 10 for i in range(n)] # followed by a list of constraints
)
4) Building Constraints (to be posted)
In the following:
v, w, brefer to single variablesx, y, zrefer to 1-dimensional arrays of variablesm, m1, m2refer to 2-dimensional (matrix) of variables
AllDifferent
Some variables (or expressions) must take different values.
AllDifferent(x[0], x[3], x[8]) # the three variable must take different values
AllDifferent(x) # all variables in x must take different values
AllDifferent(x, excepting=0) # all variables in x, different from 0, must take different values
AllDifferent(abs(x[1]-x[0]), abs(x[2]-x[1]), abs(x[3]-x[2])) # with a sequence of expressions
AllDifferent(abs(x[i+1]-x[i]) for i in range(3)) # with a generator of expressions
AllDifferent(m, matrix=True) # all rows and columns must have different values
AllDifferent(m, matrix=True, excepting=0) # (while ignoring the value 0)
AllEqual
Some variables (or expressions) must take equal values.
AllEqual(x[0], x[3], x[8]) # the three variables must take equal values
AllEqual(abs(x[1]-x[0]), abs(x[2]-x[1]), abs(x[3]-x[2])) # the three expressions must take equal values
BinPacking
A list of items, whose sizes are given, must be put in different bins in such a way that a condition in terms of capacity is respected for each bin.
x = VarArray(size=6, dom={0, 1, 2}) # 6 items to possibly be put in bins 0, 1 and 2
BinPacking(x, sizes=[8,7,3,9,5,7]) <= 12 # the capacity of each bin is 12
BinPacking(x, sizes=[8,7,3,9,5,7], limits=[9,12,11]) # capacity of bins 0, 1 and 2 are 9, 12 and 11
BinPacking(x, sizes=[8,7,3,9,5,7], loads=[y[0],y[2],y[4]]) # load of bins given by variables of y
Cardinality
The number of occurrences of certain values, taken by the variables of a list, must be restrained by an integer, a variable or an interval.
Cardinality(x, occurrences={0:3, 1:2, 2:3}) # 0 must occur 3 times, 1 two times, 2 ...
Cardinality(x, occurrences={0:3, 1:range(2,5), 2:3}) # 1 must occur between 2 and 4 times
Cardinality(x, occurrences={i:y[i] for i in range(3)}) # i must occur y[i] times
Channel
A correspondence between indexes and values of a single list has to be respected. This may also be imposed for two lists, or between a list of variables 0/1 and an integer variable.
x = VarArray(size=5, dom=range(5))
y = VarArray(size=5, dom=range(5))
Channel(x) # imposes x[i] = j <=> x[j] = i
Channel(x,y) # imposes x[i] = j <=> y[j] = i
z = VarArray(size=6, dom={0,1})
v = Var(range(6))
Channel(z,v) # imposes z[i] = 1 <=> v=i
Circuit
The values taken by some variables must form a circuit, with the assumption that each pair (i, x[i]) represents an arc.
x = VarArray(size=6, dom=range(6))
Circuit(x) # circuit of any size (self-loop are ignored)
Circuit(x, size=3) # circuit of size 3
Circuit(x, size=v) # circuit of size given by v
Count
The number of variables from a specified list that take their values from a specified set (often, a single value) must respect a numerical condition.
Count(x, value=1) >= 1 # at least 1 variable of x must take the value 1
AtLeastOne(x, value=1) # (equivalent form)
Count(x, value=0) <= 1 # at most 1 variable of x must take the value 0
AtMostOne(x, value=0) # (equivalent form)
Count(x, value=1) == 1 # exactly 1 variable of x must take the value 1
ExactlyOne(x, value=1) # (equivalent form)
Count(x, value=1) == v # the count must be equal to the value of v
Count(x, values=[1,2]) == 3 # excatly 3 variables must take their values in {1, 2}
Count([x[0]+x[1], x[1]+x[2], x[2]+x[3]], value=3) == 2 # with expressions
Exist(x[i] != y[i] for i in range(n)) # at least one expression must evaluate to 1 (true)
NotExist(x[i] != y[i] for i in range(n)) # none expression must evaluate to 1
AllHold(x[i] != y[i] for i in range(n)) # all expressions must evaluate to 1
Hamming(x, y) > 3 # the Hamming distance must be greater than 3
Cumulative
The cumulated height of some tasks must respect a numerical condition; this for each time point when considering the tasks that overlap that point.
x = VarArray(size=5, dom=range(8))
lengths = [3,2,2,4,2]
heights = [3,2,2,2,3]
Cumulative(origins=x, lengths=lengths, heights=heights) <= 5
Cumulative(tasks=[(x[i],lengths[i],heights[i]) for i in range(5)]) <= 5
Cumulative(Task(origin=x[i],length=lengths[i],height=heights[i]) for i in range(5)) <= 5
Cumulative(
tasks=[Task(origin=x[i],length=lengths[i],height=heights[i]) for i in range(5)]
) <= 5
Decreasing / Increasing
The values assigned to the variables of a list must be in decreasing (resp. increasing) order.
[x[i] >= x[i+1] for i in range(n-1)] # values in x (array of size n) are in decreasing order
Decreasing(x) # equivalent form
[x[i] + t[i] < x[i+1] for i in range(n-1)] # constants from a list t are considered
Increasing(x, lengths=t, strict=True) # equivalent form
Element
The element of a list of variables (or integers) at a specified index given by a variable (of the model) must respect a numerical condition. A variant exists for two-dimensional lists (matrices) by using two indexes.
x[v] >= 1 # v is a variable (of the model)
x[v] == w
m[v][w] == 0 # m is a two-dimensional lists
Extension (Table)
A constraint Extension (or table constraint) enumerates the tuples of values that are allowed or forbidden for a sequence of variables.
x = VarArray(size=4, dom={1,2,3})
x[0] in {1,3} # unary positive constraint (allowed values)
x[2] not in {2,3} # unary negative constraint (forbidden values)
x in {(1,2,3,2), (2,1,1,2), (2,3,2,1), (3,1,2,3)} # ordinary positive table
(x[3],x[1],x[0],x[2]) not in {(1,2,3,2), (2,1,1,2), (3,1,2,3)} # ordinary negative table
(x[0],x[1],x[2]) in {(1,ANY,2), (2,1,ANY), (3,1,3)} # starred table
Intension
A constraint Intension corresponds to a Boolean expression that may involve variables, constants and various (arithmetic, relational and logical) operators.
v + w < 10
abs(x[0 - x[1]) >= 7
(v < 2) | (w == 4) # use of the logical operator 'or' with '|'
either(v < 2, w == 4) # (equivalent form)
(v < 2) & (w == 4) # use of the logical operator 'and' with '&'
both(v < 2, w == 4) # (equivalent form)
Knapsack
Some items must be packed in a knapsack with certain weight and profit restrictions; each item is associated with 2 attributes: its weight and its profit.
x = VarArray(size=5, dom={0, 1}) # 5 possible items to be put in the knapsack
Knapsack(x, weights=[4,8,3,5,7], wlimit=20, profits=[2,3,4,4,3]) >= 12 # with a weight condition '<= 20'
Knapsack(x, weights=[4,8,3,5,7], wcondition=lt(20), profits=[2,3,4,4,3])) >= 12 # with a weight condition '< 20'
Lex
The sequence of values assigned to a list of variables must be lexicographically less than (resp, greater than) the sequence of values assigned to a second list of variables.
LexIncreasing(x,y) # x is less than or equal to y
LexIncreasing(x, y, strict=True) # x is strictly less than y
LexDecreasing(x, y, z, strict=True) # x is greater than or equal to y, itself greater than or eqaul to z
LexDecreasing(m, matrix=True) # all rows are lexicographically ordered as well as all columns
MDD
The (sequence of) values assigned to the variables of a list must correspond to a path going from the root of a specified MDD (Multi-valued Decision Diagram) to its (unique) terminal node.
r, n1, n2, n3, n4, n5, t = "r", "n1", "n2", "n3", "n4", "n5", "t" # names of nodes
transitions = [(r,0,n1), (r,1,n2), (r,2,n3), (n1,2,n4), (n2,2,n4), (n3,0,n5), (n4,0,t), (n5,0,t)]
M = MDD(transitions)
(x[0],x[1],x[2]) in M # values assigned to variables in x must correspond to a path in the MDD M
Maximum / Minimum
The maximum (resp. minimum) value in a list of variables (or expressions) must respect a numerical condition.
Maximum(x) > 1 # the maximum value in x must be greater than 1
Minimum(x) == v # the value of v corresponds to the minimum value in x
Maximum(x[0]+x[1], x[1]+x[2], x[2]+x[3]) >= 5 # when using expressions
NValues
The number of distinct values in a list of variables (or expressions) must respect a numerical condition.
NValues(x) <= 2 # the number of distinct values assigned to variables in x must be less or equal to 2
NValues(x) == v # the number of distinct values assigned to variables in x is equal to the value of v
NValues(x[0]+x[1], x[1]+x[2], x[2]+x[3], x[3]+x[4]) > 2 # when using expressions
NoOverlap
One dimensional: some objects (e.g., tasks), defined by their origins (e.g., starting times) and lengths (e.g., durations), must not overlap. </br> Multi-dimensional: some objects of multi-dimensional form must not overlap., i.e., there must exist at least one dimension where one box is after the other.
NoOverlap(origins=x, lengths=[3,5,2,4]) # one-dimensional form
NoOverlap(origins=x, lengths=y)
NoOverlap(origins=m1, lengths=[[5,4], [2,3], [3,2], [3,4]]) # two-dimensional form
NoOverlap(origins=m1, lengths=m2)
Precedence
If a variable v of a list x of variables is assigned the i+1th value of a list t of values, then another variable preceding v in x, must be assigned the ith value of t.
Precedence(x, values=[0,1]) # if 1 is assigned, 0 must be assigned before by another variable of x.
Precedence(x) # (the property must hold when considering the ordered set of possible values)
Regular
The (sequence of) values assigned to the variables of a list must belong to a regular language specified by an automaton (i.e., forms a word that can be recognized by a deterministic, or non-deterministic, finite automaton).
a, b, c, d, e = "a", "b", "c", "d", "e" # names of states
t = [(a,0,a), (a,1,b), (b,1,c), (c,0,d), (d,0,d), (d,1,e), (e,0,e)]
A = Automaton(start=a, transitions=t, final=e)
x in A # the tuple/word formed by values assigned to variables in x must be accepted by Automaton A
Sum
A sum of variables or expressions must respect a numerical condition.
Sum(x) == 12 # simple sum
Sum(x[i] * c[i] for i in range(5)) > 28 # weighted sum
x * c > 28 # equivalent form (dot product)
Sum(x[i] >= 2 for i in range(4)) >= 3 # sum of expressions
5) Specifying an objective
It is possible to maximize or to minimize an objective. Here are some examples that corresponds to minimizing:
minimize(v) # the value of the (single) variable v
minimize(v + w * 10) # the value of an expression
minimize(Sum(x)) # the sum of x
minimize([v, w] * [3, 2]) # a dot product
minimize(Minimum(x)) # the minimum value in x
minimize(Maximum(x)) # the maximum value in x
minimize(NValues(x)) # the number of different values in x
minimize(Sum(x) - Maximum(y) * 3) # the value of a complex expression