Source code for pyaicad.mdd

"""Compiling a model into a multi-valued decision diagram (MDD).

>>> import pyaicad as ac
>>> m = ac.Model()
>>> x = m.int_vars(3, domain=range(3))
>>> m.add(ac.all_different(x))
>>> mdd = ac.Compiler(m).compile()
>>> mdd.count()
6
"""

from __future__ import annotations

import operator
from typing import Any, List, Optional, Sequence, Union

from . import _core
from .errors import ModelError
from .model import Model, Var

__all__ = ["Compiler", "MDD"]

_USIZE_MAX = 2**64 - 1

_MERGE = {
    "less_relaxed": _core.PyMergeHeuristic.LessRelaxed,
    "most_likely": _core.PyMergeHeuristic.MostLikely,
    "state_similarity": _core.PyMergeHeuristic.StateSimilarity,
}


def _merge_heuristic(name: str) -> Any:
    try:
        return _MERGE[name]
    except KeyError:
        raise ValueError(f"merge must be one of {sorted(_MERGE)}, got {name!r}") from None


def _ordering(order: Union[str, Sequence[Union[Var, int]]], model: Model) -> Any:
    if isinstance(order, str):
        if order != "auto":
            raise ValueError(f"order must be 'auto' or a sequence of variables, got {order!r}")
        return _core.PyOrderingHeuristic.MinDomMaxLinked()
    indices = [v.index if isinstance(v, Var) else operator.index(v) for v in order]
    if sorted(indices) != sorted(set(indices)) or any(
        not 0 <= i < model.num_vars for i in indices
    ):
        raise ModelError("order must list distinct variables of the model")
    return _core.PyOrderingHeuristic.Custom(indices)


def _iterations(max_iterations: Optional[int]) -> Optional[int]:
    """``max_iterations`` checked: ``None`` (no limit) or an integer of at least 1."""
    if max_iterations is None:
        return None
    max_iterations = operator.index(max_iterations)
    if max_iterations < 1:
        raise ValueError(f"max_iterations must be at least 1, got {max_iterations}")
    return max_iterations


[docs] class Compiler: """Compiles a model into decision diagrams. The compiler is made for a model and the heuristics that drive the compilation; it then hands out diagrams, as exact or as relaxed as asked: :meth:`compile`. It works on the model as it is when the compiler is created. Each diagram is independent of the others and can be refined further (:meth:`MDD.refine`) until it is frozen (:meth:`MDD.freeze`). >>> import pyaicad as ac >>> m = ac.Model() >>> x = m.int_vars(3, domain=range(3)) >>> m.add(ac.all_different(x)) >>> mdd = ac.Compiler(m).compile() >>> mdd.count() 6 Args: model: The model to compile. order: ``"auto"`` to let the compiler choose the order of the layers, or a sequence listing the variables from the first layer to the last. merge: How the nodes of a layer that is too wide are merged: ``"state_similarity"`` (the default), ``"less_relaxed"`` or ``"most_likely"``. Only used by relaxed diagrams. constraints: Compile only these constraints, given as positions in ``model.constraints``. By default all of them. Only the variables in their scope get a layer. """ def __init__( self, model: Model, *, order: Union[str, Sequence[Union[Var, int]]] = "auto", merge: str = "state_similarity", constraints: Optional[Sequence[int]] = None, ) -> None: if constraints is not None: constraints = [operator.index(c) for c in constraints] if any(not 0 <= c < model.num_constraints for c in constraints): raise ModelError("constraints must be positions in model.constraints") self._model = model.copy() self._ordering = _ordering(order, model) self._merge = _merge_heuristic(merge) self._constraints = constraints self._native = _core.Compiler(model._native_problem()) @property def model(self) -> Model: """The model this compiler was made for, as it was then.""" return self._model
[docs] def compile(self, width: Optional[int] = None, max_iterations: Optional[int] = None) -> "MDD": """A new diagram of the model. Without ``width`` the diagram is exact: its paths are exactly the solutions of the model. **An exact diagram can grow without bound and fill the memory**, so give a ``width`` for models whose size you do not know. With ``width``, the diagram is relaxed: no layer has more than ``width`` nodes, and every solution of the model is still a path, but some paths are not solutions. ``max_iterations`` is the most passes that the refinement makes (a pass visits every layer once); by default it goes on until nothing more can be split. The later passes tighten a diagram little for what they cost, so a limit trades a looser diagram, still a valid relaxation, for time. At least 1. """ if width is not None: width = operator.index(width) if width < 1: raise ValueError(f"width must be at least 1, got {width}") max_iterations = _iterations(max_iterations) native = self._native.compile( constraints=self._constraints, max_width=_USIZE_MAX if width is None else width, pyordering=self._ordering, pymerge=self._merge, max_iterations=max_iterations, ) return MDD(self._model, native, width)
def __repr__(self) -> str: return f"Compiler({self._model!r})"
[docs] class MDD: """A compiled diagram. Returned by :meth:`Compiler.compile`. Each layer branches on one variable; a path from the root to the sink assigns every variable in the diagram. In an exact diagram the paths are the solutions, in a relaxed one they are a superset of them: use :meth:`Model.check` to know whether a path is a solution. """ def __init__(self, model: Model, native: Any, width: Optional[int]) -> None: self._model = model self._native = native self._width = width @property def model(self) -> Model: """The model this diagram was compiled from, as it was when compiled.""" return self._model @property def width(self) -> Optional[int]: """The width bound it was compiled with, ``None`` for an exact diagram.""" return self._width @property def is_unsat(self) -> bool: """Whether the model is proved to have no solution. A relaxed diagram can prove it too.""" return bool(self._native.is_unsat())
[docs] def refine(self, width: Optional[int] = None, max_iterations: Optional[int] = None) -> None: """Tightens the diagram in place, up to ``width`` nodes per layer (``None``: exact). A diagram compiled with a small width can be refined step by step, each step keeping the solutions and removing paths that are not. Refining to a width below the current one merges nodes again, giving a looser diagram. Fails on a frozen diagram. ``max_iterations`` limits the passes of this refinement, as in :meth:`Compiler.compile`, and is chosen at each call: many passes to a small width, then few to a large one. """ if self.is_frozen: raise RuntimeError("this diagram is frozen and cannot be refined") if width is not None: width = operator.index(width) if width < 1: raise ValueError(f"width must be at least 1, got {width}") self._native.refine( _USIZE_MAX if width is None else width, _USIZE_MAX if max_iterations is None else _iterations(max_iterations), ) self._width = width
[docs] def freeze(self) -> "MDD": """Drops what only refining needs and keeps the diagram. Returns the diagram itself. A diagram that can still be refined keeps its compilation alive: the constraints, their properties and the heuristics, which is often most of the memory. Freeze it once it is tight enough. Everything but :meth:`refine` keeps working, and freezing twice does nothing. """ self._native.freeze() return self
@property def is_frozen(self) -> bool: """Whether :meth:`freeze` was called: the diagram cannot be refined any more.""" return bool(self._native.is_frozen())
[docs] def count(self) -> int: """The number of paths. For an exact diagram, the number of solutions of the model. For a relaxed one it is an upper bound on that number. 0 when the model is unsatisfiable. """ return int(self._native.count_solutions())
@property def scope(self) -> List[Var]: """The variables the diagram branches on, in the order they were declared. All the variables of the model unless some are in no compiled constraint: they have no layer, and :meth:`solution` and :meth:`sample` give them the first value of their domain. """ variables = self._model.variables return [variables[index] for index in self._native.scope()]
[docs] def solution(self) -> Optional[List[int]]: """A solution read off the diagram, as one value per variable of the model, or ``None``. The solution is a path of exact nodes, so it satisfies the compiled constraints. An exact diagram has one whenever the model is satisfiable. A relaxed diagram may hold solutions that this does not find: ``None`` proves nothing unless :attr:`is_unsat`. """ found = None if self.is_unsat else self._native.get_solution(False) return None if found is None else self._assignment(found)
[docs] def sample(self, n: int = 1) -> List[List[int]]: """``n`` paths drawn at random, as one value per variable of the model. In an exact diagram every solution is equally likely to be drawn. A path of a relaxed diagram is not necessarily a solution: check it with :meth:`Model.check`. Call :func:`pyaicad.set_seed` first to make them reproducible. Empty if the model is unsatisfiable. """ if self.is_unsat: return [] return [ self._assignment(self._native.get_solution(True)) for _ in range(operator.index(n)) ]
def _assignment(self, found: Any) -> List[int]: """The assignment of the model for a path given as ``(values, variable indices)``.""" values, indices = found assignment = [self._model.domain(v)[0] for v in self._model.variables] for index, value in zip(indices, values): assignment[index] = value return assignment @property def widths(self) -> List[int]: """The number of nodes of each layer, from the root to the sink (which is a layer).""" return [self._native.number_nodes_in_layer(i) for i in range(self._native.number_layers())] @property def num_layers(self) -> int: """The number of layers, the sink's included.""" return int(self._native.number_layers())
[docs] def to_dot(self) -> str: """The diagram in Graphviz's DOT format.""" return str(self._native.as_graphviz())
def __repr__(self) -> str: kind = "exact" if self._width is None else f"relaxed, width {self._width}" return f"MDD({kind}, {self.num_layers} layers)"