Compiling a problem

A Compiler turns a problem into a decision diagram, an Mdd. In an exact diagram every path from the root to the sink is one solution of the problem, 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.

The examples of this chapter and the next use a latin square, which this function builds, with its grid of variables:

use std::sync::Arc;

use aicad::constraints::all_different;
use aicad::mdd::Mdd;
use aicad::modelling::{Problem, VariableIndex, equal};
use aicad::sampling::{sample_solution, uniform_weights};

/// A latin square of order `n`: every row and every column holds each of `0..n` once.
pub fn latin_square(n: usize) -> (Problem, Vec<Vec<VariableIndex>>) {
    let mut problem = Problem::default();
    let grid: Vec<Vec<VariableIndex>> = (0..n)
        .map(|_| problem.add_variables(n, (0..n as isize).collect()))
        .collect();
    for row in &grid {
        all_different(&mut problem, row.clone());
    }
    for j in 0..n {
        all_different(&mut problem, grid.iter().map(|row| row[j]).collect());
    }
    (problem, grid)
}

The diagram is read through methods of Mdd, and two helpers keep the examples short: the width of every layer, and a sampled path put back in the order of the variables (a path lists its values in the order of the layers):

/// The number of nodes of every layer.
pub fn widths(mdd: &Mdd) -> Vec<usize> {
    (0..mdd.number_layers())
        .map(|layer| mdd.number_nodes_in_layer(layer))
        .collect()
}

/// A path drawn with every solution equally likely, as an assignment: one value per variable of
/// the problem, in the order of their indices.
pub fn sample_assignment(mdd: &Mdd) -> Vec<isize> {
    let path = sample_solution(mdd, &uniform_weights(mdd));
    let (values, variables) = mdd.solution_from_path(&path);
    // A path lists its values in the order of the layers: put them back in variable order.
    let mut assignment = vec![0; values.len()];
    for (value, variable) in values.into_iter().zip(variables) {
        assignment[variable.0] = value;
    }
    assignment
}

Compiling

Compiler::new takes the problem (as an Arc, since compilation shares it), the heuristics and the constraints to compile. It starts from the loosest diagram; refine(width, max_iterations) tightens it up to width nodes per layer in at most max_iterations passes. usize::MAX lifts a limit: with both lifted the diagram is as exact as the propagation allows.

    use aicad::mdd::Compiler;
    use aicad::mdd::heuristics::CompilationHeuristic;

    let (problem, _grid) = latin_square(4);
    let constraints: Vec<_> = problem.iter_constraints().collect();
    let problem = Arc::new(problem);

    // A compiler is made for a problem, the constraints to compile and the heuristics that drive
    // the compilation. `refine(usize::MAX)` lifts the width limit: the diagram is exact.
    let mut compiler = Compiler::new(
        problem.clone(),
        CompilationHeuristic::default(),
        &constraints,
    );
    compiler.refine(usize::MAX, usize::MAX);
    let mdd = compiler.mdd();
    println!("solutions: {}", mdd.count_solutions()); // 576 latin squares of order 4

A compiler works on the problem it was given: the Arc makes the problem final once compiled. To add a clue, build the problem again, or before wrapping it.

    // The compiler owns an `Arc<Problem>`, so a problem is final once compiled: to add a clue,
    // build the problem again (or before wrapping it).
    let (mut problem, grid) = latin_square(4);
    equal(&mut problem, grid[0][0], 2);
    let constraints: Vec<_> = problem.iter_constraints().collect();
    let mut compiler = Compiler::new(
        Arc::new(problem),
        CompilationHeuristic::default(),
        &constraints,
    );
    compiler.refine(usize::MAX, usize::MAX);
    println!("with grid[0][0] = 2: {}", compiler.mdd().count_solutions()); // 576 / 4

Heuristics

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

ordering

the variable of each layer, from the root to the sink. OrderingHeuristic::MinDomMaxLinked, the default, starts with the variable of smallest domain, then takes the one most linked to those already placed. OrderingHeuristic::Custom gives your own order, as variable indices.

merge

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

    use aicad::mdd::Compiler;
    use aicad::mdd::heuristics::{
        CompilationHeuristic, MergeHeuristic, OrderingHeuristic, SelectHeuristic,
    };

    let (problem, grid) = latin_square(4);
    let constraints: Vec<_> = problem.iter_constraints().collect();
    let problem = Arc::new(problem);

    // These are the defaults, written out. `MinDomMaxLinked` starts with the variable of smallest
    // domain and then takes the one most linked to those already placed.
    let auto = CompilationHeuristic {
        ordering: OrderingHeuristic::MinDomMaxLinked,
        merge: MergeHeuristic::StateSimilarity,
        selection: SelectHeuristic::Greedy,
    };
    let mut compiler = Compiler::new(problem.clone(), auto, &constraints);
    compiler.refine(usize::MAX, usize::MAX);
    println!("nodes per layer, auto order: {:?}", widths(compiler.mdd()));

    // Any other order is a list of variable indices, from the first layer to the last. It changes
    // the size of the diagram, not the solutions it holds: here the grid is filled row by row.
    let row_by_row: Vec<usize> = grid.iter().flatten().map(|variable| variable.0).collect();
    let by_rows = CompilationHeuristic {
        ordering: OrderingHeuristic::Custom(row_by_row),
        ..CompilationHeuristic::default()
    };
    let mut other = Compiler::new(problem, by_rows, &constraints);
    other.refine(usize::MAX, usize::MAX);
    println!("nodes per layer, row by row: {:?}", widths(other.mdd()));

Reading the diagram

A sample draws a path with every value of a layer equally likely, and in an exact diagram every solution is then equally likely. set_seed makes the draws reproducible.

    aicad::set_seed(0);
    for _ in 0..3 {
        let values = sample_assignment(mdd);
        assert!(problem.is_solution(&values));
        println!("{values:?}");
    }
    let (values, _variables) = mdd.get_solution().expect("the diagram has a solution");
    println!("one solution: {values:?}");

get_solution returns the values with the variables they belong to, in the order of the layers.

Unsatisfiable problems

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

    let (mut problem, grid) = latin_square(4);
    equal(&mut problem, grid[0][0], 2);
    equal(&mut problem, grid[0][1], 2); // the same value twice in the first row
    let constraints: Vec<_> = problem.iter_constraints().collect();
    let mut compiler = Compiler::new(
        Arc::new(problem),
        CompilationHeuristic::default(),
        &constraints,
    );
    compiler.refine(usize::MAX, usize::MAX);
    let impossible = compiler.mdd();
    println!(
        "unsatisfiable: {} - solutions: {} - {:?}",
        impossible.is_unsat(),
        impossible.count_solutions(),
        impossible.get_solution()
    );

Drawing

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

    let mut small = Problem::default();
    let x = small.add_variables(3, vec![0, 1, 2]);
    let constraint = all_different(&mut small, x);
    let mut compiler = Compiler::new(
        Arc::new(small),
        CompilationHeuristic::default(),
        &[constraint],
    );
    compiler.refine(usize::MAX, usize::MAX);
    let dot = compiler.mdd().as_graphviz(); // `dot -Tpdf`
    println!("{}", &dot[..60]);

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.