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.
orderingthe 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::Customgives your own order, as variable indices.mergewhich 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.