Python API reference

Modelling

class pyaicad.Model[source]

A constraint satisfaction problem: variables with finite integer domains and constraints.

>>> m = Model()
>>> grid = m.int_vars((2, 2), domain=range(1, 3))   # a 2 x 2 grid of variables
>>> m.add(all_different(grid[0]), all_different([row[0] for row in grid]))
int_var(domain)[source]

A variable taking one of the integer values of domain.

Parameters:

domain (Iterable[int])

Return type:

Var

bool_var()[source]

A variable taking the value 0 or 1.

Return type:

Var

int_vars(shape, domain)[source]

Variables sharing a domain.

shape is a number n, giving a list of n variables, or a tuple, giving nested lists: (9, 9) is a list of 9 rows of 9 variables.

Parameters:
Return type:

Any

bool_vars(shape)[source]

Boolean variables, shaped like int_vars().

Parameters:

shape (int | Tuple[int, ...])

Return type:

Any

set_position(var, position)[source]

Attaches coordinates to a variable (a cell’s row and column, say).

Learned models can use them as positional information; they have no meaning for the constraints.

Parameters:
Return type:

None

add(*constraints)[source]

Adds constraints. Each argument is a constraint or an iterable of constraints.

Parameters:

constraints (Constraint | Iterable[Constraint])

Return type:

None

property variables: List[Var]

All the variables, in the order of an assignment.

property constraints: Tuple[Constraint, ...]

All the constraints, in the order they were added.

domain(var)[source]

The current domain of a variable.

Parameters:

var (Var)

Return type:

Tuple[int, …]

check(assignment)[source]

Whether assignment (one value per variable) satisfies the model.

Parameters:

assignment (Sequence[int])

Return type:

bool

is_constraint_satisfied(constraint, assignment)[source]

Whether assignment (one value per variable) satisfies one constraint of the model.

Iterate over constraints to find which ones an assignment violates.

Parameters:
Return type:

bool

copy()[source]

An independent copy: later changes to one do not affect the other.

The variables of the original are valid in the copy, so a constraint built on them can be added to either.

Return type:

Model

class pyaicad.Var(index, owner)[source]

A decision variable of a model. Created by Model, never directly.

var.index is its position in an assignment.

Parameters:
class pyaicad.Constraint[source]

A constraint, built by one of the functions below and added with Model.add().

scope is the tuple of variables it constrains.

pyaicad.all_different(variables)[source]

The variables take pairwise different values.

Parameters:

variables (Iterable[Var])

Return type:

Constraint

pyaicad.not_equal(x, y)[source]

x and y take different values.

Parameters:
Return type:

Constraint

pyaicad.equal(x, value)[source]

x takes value. Adding it to a model shrinks the domain of x to that value.

Parameters:
Return type:

Constraint

pyaicad.among(variables, values, lb, ub)[source]

Between lb and ub of the variables take a value in values.

Parameters:
Return type:

Constraint

pyaicad.at_least(variables, values, lb)[source]

At least lb of the variables take a value in values.

Parameters:
Return type:

Constraint

pyaicad.sum_equals(variables, target)[source]

The variables add up to target. Values may be negative.

Parameters:
Return type:

Constraint

pyaicad.gcc(variables, bounds)[source]

Global cardinality: each value of bounds occurs between its lo and hi times.

bounds is either a mapping {value: (lo, hi)} or an iterable of (value, lo, hi). A value that is not in bounds is unconstrained.

Parameters:
Return type:

Constraint

pyaicad.regular(variables, transitions, initial_state, accepting_states)[source]

The variables, read in order, form a word accepted by an automaton.

transitions[state][symbol] is the state reached from state on a symbol, or None if there is no transition. The columns are the sorted values found in the domains of the variables at the time the constraint is added to the model.

Parameters:
Return type:

Constraint

pyaicad.table(variables, tuples)[source]

The variables take the values of one of the tuples.

Column j of a tuple is the value of the j-th variable. Duplicate tuples are ignored, and a tuple with a value that is not in the domain of its variable is never used. With no tuple at all the constraint cannot be satisfied.

>>> import pyaicad as ac
>>> m = ac.Model()
>>> x, y = m.int_vars(2, domain=range(3))
>>> m.add(ac.table([x, y], [(0, 1), (1, 2), (2, 0)]))
>>> m.check([1, 2]), m.check([1, 1])
(True, False)
Parameters:
Return type:

Constraint

pyaicad.disjunctive(variables, release, deadline, duration, precedences=None, setup_times=None, setup_relaxation='last_job', padding=False)[source]

The variables are a sequence of all the jobs, processed one at a time (a unary resource).

variables[k] is the job processed in position k: its value is a job number 0..n-1, where n is the number of variables, so the values are a permutation of the jobs. Job j has release date release[j], deadline deadline[j] (the latest time at which it may be completed) and duration duration[j]. Each job starts as soon as the machine is free and the job is released, and runs without interruption.

precedences is an optional list of pairs (i, j) of job numbers: job i is processed before job j (not necessarily right before). The precedences must not form a cycle.

setup_times is an optional n by n matrix: setup_times[i][j] is the time that has to pass between the end of job i and the start of job j when j follows i. The first job needs no setup, the diagonal is ignored, and no entry may be negative.

setup_relaxation says what a node of a relaxed diagram remembers about the job that the next setup depends on, and only matters with setup_times. It does not change the solutions, only how many nodes the compilation needs and how well a relaxed diagram prunes. "last_job" (the default) keeps one job number per node, the cheapest. "last_set" keeps the set of these jobs, which gives tighter bounds when nodes are merged. "arc_times" keeps one time per job, the tightest and the most expensive (O(n) numbers per node and per edge).

With padding=True the value n (one more than the last job number) is a dummy job that fills the end of the sequence, and the number of variables is free: the sequence has the jobs that the machine processes, each at most once and in order, followed by dummies. Dummies take no time and no setup, and cannot be followed by a job. The domains must contain n. Not every job has to appear (another constraint decides on which machine each one runs), a precedence only binds the jobs that appear, and the lists still have one entry per job.

>>> import pyaicad as ac
>>> m = ac.Model()
>>> x = m.int_vars(3, domain=range(3))
>>> # Job 1 has to be over by time 4: it cannot come after job 0.
>>> m.add(ac.disjunctive(x, release=[0, 0, 0], deadline=[10, 4, 10], duration=[3, 2, 2]))
>>> m.check([1, 0, 2]), m.check([0, 1, 2])
(True, False)
>>> m = ac.Model()
>>> x = m.int_vars(3, domain=range(3))
>>> m.add(ac.disjunctive(x, [0, 0, 0], [10, 4, 10], [3, 2, 2], precedences=[(2, 1)]))
>>> m.check([2, 1, 0]), m.check([1, 0, 2])
(True, False)
>>> # Two slots for three jobs: the machine runs two of them, or only one and a dummy (3).
>>> m = ac.Model()
>>> x = m.int_vars(2, domain=range(4))
>>> m.add(ac.disjunctive(x, [0, 0, 0], [5, 5, 5], [2, 2, 2], padding=True))
>>> m.check([0, 2]), m.check([1, 3]), m.check([3, 3]), m.check([3, 1]), m.check([0, 0])
(True, True, True, False, False)
Parameters:
Return type:

Constraint

Compiling

class pyaicad.Compiler(model, *, order='auto', merge='state_similarity', constraints=None)[source]

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: 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 (MDD.refine()) until it is frozen (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
Parameters:
  • model (Model) – The model to compile.

  • order (Union[str, Sequence[Union[Var, int]]]) – "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 (str) – 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 (Optional[Sequence[int]]) – Compile only these constraints, given as positions in model.constraints. By default all of them. Only the variables in their scope get a layer.

property model: Model

The model this compiler was made for, as it was then.

compile(width=None, max_iterations=None)[source]

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.

Parameters:
  • width (int | None)

  • max_iterations (int | None)

Return type:

MDD

class pyaicad.MDD(model, native, width)[source]

A compiled diagram. Returned by 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 Model.check() to know whether a path is a solution.

Parameters:
  • model (Model)

  • native (Any)

  • width (Optional[int])

property model: Model

The model this diagram was compiled from, as it was when compiled.

property width: int | None

The width bound it was compiled with, None for an exact diagram.

property is_unsat: bool

Whether the model is proved to have no solution. A relaxed diagram can prove it too.

refine(width=None, max_iterations=None)[source]

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 Compiler.compile(), and is chosen at each call: many passes to a small width, then few to a large one.

Parameters:
  • width (int | None)

  • max_iterations (int | None)

Return type:

None

freeze()[source]

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 refine() keeps working, and freezing twice does nothing.

Return type:

MDD

property is_frozen: bool

the diagram cannot be refined any more.

Type:

Whether freeze() was called

count()[source]

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 type:

int

property scope: 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 solution() and sample() give them the first value of their domain.

solution()[source]

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 is_unsat.

Return type:

List[int] | None

sample(n=1)[source]

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 Model.check(). Call pyaicad.set_seed() first to make them reproducible. Empty if the model is unsatisfiable.

Parameters:

n (int)

Return type:

List[List[int]]

property widths: List[int]

The number of nodes of each layer, from the root to the sink (which is a layer).

property num_layers: int

The number of layers, the sink’s included.

to_dot()[source]

The diagram in Graphviz’s DOT format.

Return type:

str

Settings and errors

pyaicad.set_seed(seed)[source]

Seeds every source of randomness of the library, so that a run can be reproduced.

This covers weight initialisation, sampling from a diagram or a network, the choices of the search, and the shuffling done during training.

Parameters:

seed (int)

Return type:

None

pyaicad.set_num_threads(n)[source]

Sets how many threads the library may use for its parallel work: solving a batch of problems, training, and building the datasets for it.

Unless this is called, the library uses a quarter of the threads available on the machine (at least one), so that it does not take over a shared server. Raise it to use more of the machine. It can be called at any time, even between two uses of the library; work already running finishes with the threads it had.

Compiling a single diagram always uses one thread. The number of threads is unrelated to batch_size and to what runs on a GPU.

Raises:
Parameters:

n (int)

Return type:

None

pyaicad.get_num_threads()[source]

The number of threads the library uses for its parallel work: the value given to set_num_threads(), or the default (a quarter of the available threads, at least one).

Return type:

int

pyaicad.set_log_level(level)[source]

Sets how much the library logs: "off" (the default), "error", "warning", "info", "debug" or "trace".

The library logs through the standard logging module, under the logger "aicad". If your program has not configured logging, a handler writing to standard error is added to that logger so the messages are visible.

Parameters:

level (str)

Return type:

None

pyaicad.version()[source]

Returns the build of the library that is running: its version, the commit it was built from, the Rust compiler and the build settings.

>>> import pyaicad as ac
>>> ac.version().profile in ("debug", "release")
True

Benchmarks are only comparable between commits, so run them from a clean copy of a commit and keep this with the results. The same record is the first line of every file written by pyaicad.diagnostics.enable_data_log().

Return type:

BuildInfo

class pyaicad.BuildInfo(version, commit, rustc, target, profile, opt_level, features)[source]

The build of the library that is running: what was compiled into the native extension.

The version of the source tree says little about the code that runs, which may be an installed copy of another commit. Record this next to any measurement.

Parameters:
version: str

The version of the library.

commit: str | None

The full hash of the commit it was built from, or None if it could not be known (a build from a source archive without .git).

rustc: str

The Rust compiler, as printed by rustc --version; empty if it could not be run.

target: str

The compilation target, for example x86_64-unknown-linux-gnu.

profile: str

The cargo profile, "debug" or "release". A debug build is much slower.

opt_level: str

"0", "1", "2", "3", "s" or "z".

Type:

The optimisation level of the profile

features: Tuple[str, ...]

The cargo features that were on, sorted ("learning", "python").

pyaicad.HAS_LEARNING = True

bool(x) -> bool

Returns True when the argument x is true, False otherwise. The builtins True and False are the only two instances of the class bool. The class bool is a subclass of the class int, and cannot be subclassed.

exception pyaicad.AicadError[source]

Base class of the errors raised by pyaicad itself.

exception pyaicad.ModelError[source]

The model, or one of its variables or constraints, is invalid.

exception pyaicad.CheckpointError[source]

A checkpoint is missing, incomplete, or cannot be used for the requested problems.

exception pyaicad.FeatureUnavailableError[source]

The feature needs a part of pyaicad that this build does not include.

Training and the neural searches come with the learning feature of the native library.

Training

These need the full build.

Training the networks that guide the search.

A training set is a list of problems: one problem per training example. Dataset splits a list into training and validation sets; fit() trains a network on it with a named recipe. The problems you evaluate on are kept apart by you and never given to fit(); the trained network is a Checkpoint that the neural searches (pyaicad.NeuralPriorSearch, pyaicad.NeuralPriorBPSearch) solve with.

Each network has its own restrictions on the problems it can be trained on and used with; they are documented with the network in the Rust crate (neural::consformer for ConsFormer), not here.

>>> import pyaicad as ac
>>> from pyaicad import learning
>>> ckpt = learning.fit(train_problems, "consformer-mdd", checkpoint_dir="ckpt", epochs=50)
>>> results = ac.local_search(test_problems, ac.NeuralPriorBPSearch(ckpt))
class pyaicad.learning.Dataset(train, validation)[source]

The problems a network is trained on: training and validation problems.

The validation set is used during training to keep the best network. There is no test set on purpose: evaluating on problems that training could have seen proves nothing, so the problems you evaluate on are yours to keep apart and never pass to fit().

Parameters:
classmethod split(problems, validation_fraction=0.2, *, seed=None)[source]

Splits problems at random into training and validation sets.

validation_fraction is the share of the problems kept for validation, strictly between 0 and 1; both sets get at least one problem. The same seed gives the same split.

Parameters:
Return type:

Dataset

class pyaicad.learning.Network(domain_size='auto', embedding_size=128, hidden_size=128, num_heads=1, expand_size=128, num_layers=1, dropout=0.0, bias=True, positional_encoding_dimensions=0, mask_fraction=0.5, tau=0.1, learned_attention_mask=False)[source]

The architecture of a ConsFormer network.

domain_size is the number of values the network can predict: values 0 to domain_size - 1. "auto" takes the smallest size covering the problems it is trained on, which requires non-negative values.

Parameters:
  • domain_size (int | str)

  • embedding_size (int)

  • hidden_size (int)

  • num_heads (int)

  • expand_size (int)

  • num_layers (int)

  • dropout (float)

  • bias (bool)

  • positional_encoding_dimensions (int)

  • mask_fraction (float)

  • tau (float)

  • learned_attention_mask (bool)

class pyaicad.learning.Adam(lr=0.0003, beta_1=0.9, beta_2=0.999, epsilon=1e-05, amsgrad=False, weight_decay=None, grad_clip_norm=None, grad_clip_value=None)[source]

The Adam optimiser. weight_decay is an L2 penalty (None for none).

grad_clip_norm clips the L2 norm of each gradient tensor and grad_clip_value clips each element of the gradient; set at most one.

Parameters:
class pyaicad.learning.AdamW(lr=0.0003, beta_1=0.9, beta_2=0.999, epsilon=1e-05, amsgrad=False, weight_decay=0.0001, grad_clip_norm=None, grad_clip_value=None)[source]

Adam with a decoupled weight decay, which is always applied (0 for none).

grad_clip_norm clips the L2 norm of each gradient tensor and grad_clip_value clips each element of the gradient; set at most one.

Parameters:
class pyaicad.learning.SGD(lr=0.01, momentum=None, dampening=0.0, nesterov=False, weight_decay=None, grad_clip_norm=None, grad_clip_value=None)[source]

Stochastic gradient descent, with momentum if momentum is set.

dampening and nesterov only apply with a momentum. weight_decay is an L2 penalty (None for none). grad_clip_norm clips the L2 norm of each gradient tensor and grad_clip_value clips each element of the gradient; set at most one.

Parameters:
pyaicad.learning.Optimiser

one of Adam, AdamW and SGD.

Type:

An optimiser with its settings

alias of Adam | AdamW | SGD

class pyaicad.learning.Training(optimiser=<factory>, epochs=10, batch_size=32, validation_interval=10, early_stopping_patience=None, early_stopping_min_delta=0.0001, initial_weights=None, destroy='random')[source]

How the network is optimised.

optimiser is the optimiser with its learning rate and settings (Adam by default). The network is evaluated on the validation set every validation_interval epochs, and the best one so far is kept; so validation_interval must not exceed epochs.

initial_weights is the checkpoint directory of an earlier run: its weights initialise the network before the first epoch, to continue or fine-tune that run. The network settings must be the ones the weights were trained with. By default the network starts from scratch.

Parameters:
class pyaicad.learning.Recipe(name, loss, network=<factory>, training=<factory>, order='auto', merge='state_similarity', bp_rounds=0, gumbel_scale=1.0)[source]

A way of training a network: the loss, the architecture and the optimiser settings.

Use one of the named recipes in RECIPES, optionally with changes:

>>> Recipe.named("consformer-mdd").replace(epochs=50, lr=1e-3).training.epochs
50
>>> Recipe.named("consformer").replace(optimiser=SGD(momentum=0.9)).training.optimiser.lr
0.01

replace takes the name of any setting of the network, the training, or the recipe itself, and refuses names it does not know.

With the "mdd" loss, bp_rounds is the number of rounds of belief propagation (the one of pyaicad.NeuralPriorBPSearch) that label the diagram of each constraint before its weighted model count is taken: the network’s probabilities are the prior of each variable, and the diagram of a constraint is labelled with that prior tilted by what the other constraints say about the variable. The loss then sees the other constraints, and scores the weights that the search labels its diagrams with. 0, the default, labels the diagrams with the network’s probabilities as they are; the gradient is taken with respect to them, the messages of belief propagation being constants. The setting has no effect on the "classical" loss.

gumbel_scale multiplies the Gumbel noise that is added to the network’s logits before their softmax turns them into the probabilities the "mdd" loss scores. 1.0, the default, is the Gumbel-softmax relaxation of ConsFormer; 0.0 adds no noise, so the loss is the exact expectation under the plain softmax of the logits, and is deterministic (so is the validation loss that selects the best network). It applies to the whole loss, belief propagation included, and has no effect on the "classical" loss.

>>> Recipe.named("consformer-mdd").bp_rounds
0
>>> Recipe.named("consformer-mdd").replace(bp_rounds=1).bp_rounds
1
>>> Recipe.named("consformer-mdd").replace(bp_rounds=5).bp_rounds
5
>>> Recipe.named("consformer-mdd").gumbel_scale
1.0
>>> Recipe.named("consformer-mdd").replace(gumbel_scale=0.0).gumbel_scale
0.0
Parameters:
static named(name)[source]

One of the recipes of RECIPES.

Parameters:

name (str)

Return type:

Recipe

replace(**changes)[source]

A copy with some settings changed, by name.

A setting of the optimiser (lr, momentum, …) changes the optimiser the recipe has once optimiser= is applied, if given.

Parameters:

changes (Any)

Return type:

Recipe

pyaicad.learning.RECIPES: Dict[str, Recipe] = {'consformer': Recipe(name='consformer', loss='classical', network=Network(domain_size='auto', embedding_size=128, hidden_size=128, num_heads=1, expand_size=128, num_layers=1, dropout=0.0, bias=True, positional_encoding_dimensions=0, mask_fraction=0.5, tau=0.1, learned_attention_mask=False), training=Training(optimiser=Adam(lr=0.0003, beta_1=0.9, beta_2=0.999, epsilon=1e-05, amsgrad=False, weight_decay=None, grad_clip_norm=None, grad_clip_value=None), epochs=10, batch_size=32, validation_interval=10, early_stopping_patience=None, early_stopping_min_delta=0.0001, initial_weights=None, destroy='random'), order='auto', merge='state_similarity', bp_rounds=0, gumbel_scale=1.0), 'consformer-mdd': Recipe(name='consformer-mdd', loss='mdd', network=Network(domain_size='auto', embedding_size=128, hidden_size=128, num_heads=1, expand_size=128, num_layers=1, dropout=0.0, bias=True, positional_encoding_dimensions=0, mask_fraction=0.5, tau=0.1, learned_attention_mask=False), training=Training(optimiser=Adam(lr=0.0003, beta_1=0.9, beta_2=0.999, epsilon=1e-05, amsgrad=False, weight_decay=None, grad_clip_norm=None, grad_clip_value=None), epochs=10, batch_size=32, validation_interval=10, early_stopping_patience=None, early_stopping_min_delta=0.0001, initial_weights=None, destroy='random'), order='auto', merge='state_similarity', bp_rounds=0, gumbel_scale=1.0)}

The named recipes. "consformer" trains with a hand-written penalty per constraint type; "consformer-mdd" trains against the exact weighted model count of each constraint’s MDD.

pyaicad.learning.fit(data, recipe='consformer-mdd', *, checkpoint_dir, seed=None, **settings)[source]

Trains a network and keeps the best one found in checkpoint_dir.

The network with the lowest loss on the validation set is written to checkpoint_dir during training, so an interrupted run still leaves a usable one.

Parameters:
  • data (Dataset | Sequence[Model]) – A Dataset, or a list of problems, which is split 80/20 into training and validation sets (use Dataset.split() for another share). Never include the problems you evaluate on.

  • recipe (str | Recipe) – The name of a recipe in RECIPES, or a Recipe.

  • checkpoint_dir (str | PathLike[str]) – Where the network is written. Created if missing.

  • seed (int | None) – Seeds the library’s randomness (see pyaicad.set_seed()) before training, and the split of a plain list.

  • **settings (Any) – Changes to the recipe, by name, as in Recipe.replace(): fit(data, "consformer", checkpoint_dir="ckpt", epochs=50, embedding_size=64).

Returns:

The Checkpoint holding the best network.

Return type:

Checkpoint

pyaicad.learning.load(path)[source]

Opens a checkpoint written by fit(). See Checkpoint.load().

Parameters:

path (str | PathLike[str])

Return type:

Checkpoint

class pyaicad.learning.Checkpoint(path, config)[source]

A trained network on disk: a directory holding config.json and weights.mpk.

Parameters:
property domain_size: int

The number of values the network predicts.

classmethod load(path)[source]

Opens the checkpoint in directory path, checking that it is complete.

Parameters:

path (str | PathLike[str])

Return type:

Checkpoint