Relaxed diagrams and refinement

When an exact diagram is too large, compile a relaxed one: it has at most width nodes per layer. It keeps every solution as a path and adds paths that are not solutions, so its path count is an upper bound on the number of solutions.

import pyaicad as ac

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)
exact = compiler.compile().count()

mdd = compiler.compile(width=2)
print(f"width {mdd.width}: {mdd.count()} paths for {exact} solutions")
width 2: 4294967296 paths for 576 solutions

A path of a relaxed diagram is not necessarily a solution: check it against the model.

relaxed = compiler.compile(width=256)
print(f"width 256: {relaxed.count()} paths")
print("a random path is a solution:", model.check(relaxed.sample(1)[0]))
width 256: 1284378 paths
a random path is a solution: False

One compiler hands out as many diagrams as you need, each independent of the others.

Refinement

A diagram can be tightened in place instead of compiled again: refine(width) raises the budget and splits nodes where the relaxation lost information. The path count only goes down, and never below the number of solutions. refine(None) goes on until the diagram is as exact as the propagation allows.

compile and refine also take max_iterations, the most passes over the layers that the refinement makes. The later passes tighten the diagram little for what they cost, so a limit trades a looser diagram, still a relaxation, for time; it is chosen at each call.

mdd = compiler.compile(width=2)
for width in (4, 8, 32, None):
    mdd.refine(width)
    print(f"width {width}: {mdd.count()} paths, widest layer {max(mdd.widths)}")
assert mdd.count() == exact
width 4: 1971978240 paths, widest layer 4
width 8: 1191175168 paths, widest layer 8
width 32: 45193843 paths, widest layer 32
width None: 576 paths, widest layer 360

Freezing

A diagram that can be refined keeps its compilation alive: the constraints, their properties and the heuristics, which is often most of its memory. Once it is tight enough, freeze drops all that and keeps the diagram. Counting, sampling and drawing still work, refining does not.

mdd.freeze()
print("frozen:", mdd.is_frozen, "- still", mdd.count(), "paths")
try:
    mdd.refine(8)
except RuntimeError as error:
    print("refining a frozen diagram fails:", error)
frozen: True - still 576 paths
refining a frozen diagram fails: this diagram is frozen and cannot be refined

Choosing what to compile

The constraints argument compiles a subset of the constraints. A variable that is in none of them has no layer; mdd.scope lists the variables that do.

rows_only = ac.Compiler(model, constraints=range(n)).compile()
print("rows alone:", rows_only.count(), "paths over", len(rows_only.scope), "variables")
rows alone: 331776 paths over 16 variables

The merge heuristic says which nodes are joined when a layer is full; at the same width it can give tighter or looser diagrams.

column_major = [grid[i][j] for j in range(n) for i in range(n)]
for merge in ("less_relaxed", "most_likely", "state_similarity"):
    mdd = ac.Compiler(model, order=column_major, merge=merge).compile(width=4)
    print(f"merge={merge!r}: {mdd.count()} paths")
merge='less_relaxed': 1366917120 paths
merge='most_likely': 1366917120 paths
merge='state_similarity': 1678215168 paths

Solutions and proofs from relaxed diagrams

An exact diagram decides the model: it has a solution or it is unsatisfiable. A relaxed one decides less. solution() returns a solution only if the diagram holds a path of exact nodes, so None proves nothing, except when the diagram is unsatisfiable, which is a proof even for a relaxed diagram.

def pigeons(pigeons, holes):
    """Every pigeon in a hole, no two in the same hole: feasible iff pigeons <= holes."""
    model = ac.Model()
    hole = model.int_vars(pigeons, domain=range(holes))
    model.add(ac.all_different(hole))
    return model

compiler = ac.Compiler(pigeons(5, 5))
for width in (1, 4, None):
    mdd = compiler.compile(width=width)
    print(f"5 pigeons, 5 holes, width {width}: unsatisfiable={mdd.is_unsat}, solution={mdd.solution()}")

mdd = ac.Compiler(pigeons(5, 4)).compile(width=1)
print("5 pigeons, 4 holes, width 1: unsatisfiable =", mdd.is_unsat)
5 pigeons, 5 holes, width 1: unsatisfiable=False, solution=None
5 pigeons, 5 holes, width 4: unsatisfiable=False, solution=None
5 pigeons, 5 holes, width None: unsatisfiable=False, solution=[0, 1, 3, 2, 4]
5 pigeons, 4 holes, width 1: unsatisfiable = True