Compiling a model

A Compiler turns a model into a decision diagram, an MDD. In an exact diagram every path from the root to the sink is one solution of the model, so questions about the solutions are answered by reading the diagram instead of searching: how many there are, a random one, whether there is any.

import pyaicad as ac

# A 4 x 4 latin square: every row and every column holds each of 0..3 once.
n = 4
model = ac.Model()
grid = model.int_vars((n, n), domain=range(n))
model.add(ac.all_different(row) for row in grid)
model.add(ac.all_different([grid[i][j] for i in range(n)]) for j in range(n))

compiler = ac.Compiler(model)
mdd = compiler.compile()
print(mdd)
print("solutions:", mdd.count())
MDD(exact, 17 layers)
solutions: 576

A compiler is made for a model as it is at that moment. If you add constraints afterwards, make a new compiler.

Heuristics

Two heuristics drive the compilation. They decide how large the diagram gets, never what it contains.

order

the variable of each layer, from the root to the sink. "auto", the default, is the min-dom-max-linked heuristic: it starts with the variable of smallest domain, then takes the one most linked to those already placed. A list of variables gives your own order.

merge

which nodes are joined when a layer is full, so it only matters for relaxed diagrams (next chapter). The default is "state_similarity".

auto = ac.Compiler(model, order="auto").compile()
print("nodes per layer, auto order:", auto.widths)

row_by_row = [grid[i][j] for i in range(n) for j in range(n)]
by_rows = ac.Compiler(model, order=row_by_row).compile()
print("nodes per layer, row by row:", by_rows.widths)

assert by_rows.count() == auto.count()   # same solutions, other shape
nodes per layer, auto order: [1, 4, 12, 24, 24, 72, 144, 144, 312, 360, 180, 156, 72, 24, 12, 4, 1]
nodes per layer, row by row: [1, 4, 12, 24, 24, 72, 156, 180, 90, 180, 156, 72, 24, 24, 12, 4, 1]

Reading the diagram

ac.set_seed(0)
for values in mdd.sample(3):             # in an exact diagram, every solution is equally likely
    assert model.check(values)
    print(values)

print("one solution:", mdd.solution())
[2, 0, 3, 1, 3, 2, 1, 0, 1, 3, 0, 2, 0, 1, 2, 3]
[3, 0, 1, 2, 0, 2, 3, 1, 1, 3, 2, 0, 2, 1, 0, 3]
[1, 2, 3, 0, 0, 1, 2, 3, 2, 3, 0, 1, 3, 0, 1, 2]
one solution: [0, 3, 2, 1, 3, 0, 1, 2, 2, 1, 3, 0, 1, 2, 0, 3]

A solution is a list of values in the order of model.variables, like any assignment.

Unsatisfiable models

Contradictory constraints are detected during compilation, and an exact diagram is then a proof.

model.add(ac.equal(grid[0][0], 2))
model.add(ac.equal(grid[0][1], 2))       # the same value twice in the first row
impossible = ac.Compiler(model).compile()
print("unsatisfiable:", impossible.is_unsat, "- solutions:", impossible.count(), "-", impossible.solution())
unsatisfiable: True - solutions: 0 - None

Drawing

to_dot returns a Graphviz description (dot -Tpdf) of a diagram, practical for small ones.

small = ac.Model()
x = small.int_vars(3, domain=range(3))
small.add(ac.all_different(x))
print(ac.Compiler(small).compile().to_dot()[:200], "...")
digraph {
rankdir=TD;
tranksep = 3;

subgraph labels {
	L0 [shape=plaintext, label="x0"];
	L1 [shape=plaintext, label="x2"];
	L2 [shape=plaintext, label="x1"];
}
subgraph mdd {
	{rank=same; N0_0 [shap ...

Memory

An exact diagram can be too large to build, and nothing bounds the memory of an unbounded compilation. The next chapter shows how to bound the size of the diagram.