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. count_solutions returns an arbitrary-precision
integer, since a relaxed diagram can hold far more paths than any fixed-width integer.
let (problem, _grid) = latin_square(4);
let constraints: Vec<_> = problem.iter_constraints().collect();
let problem = Arc::new(problem);
let mut exact = Compiler::new(
problem.clone(),
CompilationHeuristic::default(),
&constraints,
);
exact.refine(usize::MAX, usize::MAX);
let solutions = exact.mdd().count_solutions();
// At most 2 nodes per layer: every solution is still a path, and many paths are not solutions.
let mut compiler = Compiler::new(
problem.clone(),
CompilationHeuristic::default(),
&constraints,
);
compiler.refine(2, usize::MAX);
println!(
"width 2: {} paths for {solutions} solutions",
compiler.mdd().count_solutions()
);
A path of a relaxed diagram is not necessarily a solution: check it against the problem.
// A path of a relaxed diagram is not necessarily a solution: check it against the problem.
let mut relaxed = Compiler::new(
problem.clone(),
CompilationHeuristic::default(),
&constraints,
);
relaxed.refine(256, usize::MAX);
println!("width 256: {} paths", relaxed.mdd().count_solutions());
let path = sample_assignment(relaxed.mdd());
println!(
"a random path is a solution: {}",
problem.is_solution(&path)
);
Compilers are independent: make as many as you need for the same problem.
Refinement¶
A diagram can be tightened in place instead of compiled again: refine(width, max_iterations)
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(usize::MAX, usize::MAX) goes on until the
diagram is as exact as the propagation allows.
The second argument limits the passes over the layers that the refinement makes. The later passes tighten the diagram little for what they cost, so a solver can spend many passes on a small width and only a few on a large one: the limit is chosen at each call, and what a limited call leaves is a looser diagram, still a relaxation.
let mut compiler = Compiler::new(problem, CompilationHeuristic::default(), &constraints);
compiler.refine(2, usize::MAX);
let mut previous = compiler.mdd().count_solutions();
for width in [4, 8, 32, usize::MAX] {
compiler.refine(width, usize::MAX);
let paths = compiler.mdd().count_solutions();
let widest = widths(compiler.mdd()).into_iter().max().unwrap();
println!("width {width}: {paths} paths, widest layer {widest}");
assert!(paths <= previous); // the number of paths only goes down...
assert!(paths >= solutions); // ...and never below the number of solutions
previous = paths;
}
assert_eq!(compiler.mdd().count_solutions(), solutions);
Freezing¶
A compiler keeps what refining needs: the constraints, their properties and the heuristics, which
is often most of the memory. Once the diagram is tight enough, into_mdd consumes the compiler and
keeps the diagram. In Python freeze does the same on the diagram object, and refining it
afterwards is a runtime error; in Rust it is a type error, since only a Compiler has refine.
// A compiler keeps what refining needs: the constraints, their properties and the heuristics,
// which is often most of the memory. `into_mdd` consumes it and keeps the diagram, which can
// still be counted, sampled and drawn. Refining it any more is not possible, and the types say
// so: only a `Compiler` has `refine`.
let mdd = compiler.into_mdd();
println!("frozen, still {} paths", mdd.count_solutions());
Choosing what to compile¶
The constraints given to Compiler::new are the ones that are compiled. A variable that is in none
of them has no layer; number_decisions and decision_at_layer list the variables that do.
let (problem, _grid) = latin_square(4);
// The first four constraints of `latin_square` are the rows.
let rows: Vec<ConstraintIndex> = problem.iter_constraints().take(4).collect();
let mut compiler = Compiler::new(Arc::new(problem), CompilationHeuristic::default(), &rows);
compiler.refine(usize::MAX, usize::MAX);
let mdd = compiler.mdd();
// A variable in none of the compiled constraints has no layer.
let scope: Vec<_> = (0..mdd.number_decisions())
.map(|layer| mdd.decision_at_layer(layer))
.collect();
println!(
"rows alone: {} paths over {} variables",
mdd.count_solutions(),
scope.len()
);
The merge heuristic says which nodes are joined when a layer is full; at the same width it can give
tighter or looser diagrams. MostLikely carries the probability of every value of every variable.
let (problem, grid) = latin_square(4);
let constraints: Vec<_> = problem.iter_constraints().collect();
let problem = Arc::new(problem);
let column_major: Vec<usize> = (0..4)
.flat_map(|j| (0..4).map(move |i| (i, j)))
.map(|(i, j)| grid[i][j].0)
.collect();
// `MostLikely` reads the probability of every value of every variable: here, all equal.
let uniform = vec![vec![0.25; 4]; problem.number_variables()];
for (name, merge) in [
("LessRelaxed", MergeHeuristic::LessRelaxed),
("MostLikely", MergeHeuristic::MostLikely(uniform)),
("StateSimilarity", MergeHeuristic::StateSimilarity),
] {
let heuristic = CompilationHeuristic {
ordering: OrderingHeuristic::Custom(column_major.clone()),
merge,
..CompilationHeuristic::default()
};
let mut compiler = Compiler::new(problem.clone(), heuristic, &constraints);
compiler.refine(4, usize::MAX);
println!("{name}: {} paths", compiler.mdd().count_solutions());
}
Solutions and proofs from relaxed diagrams¶
An exact diagram decides the problem: it has a solution or it is unsatisfiable. A relaxed one
decides less. get_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.
/// Every pigeon in a hole, no two in the same hole: feasible iff `pigeons <= holes`.
fn pigeons(pigeons: usize, holes: usize) -> (Arc<Problem>, Vec<ConstraintIndex>) {
let mut problem = Problem::default();
let hole = problem.add_variables(pigeons, (0..holes as isize).collect());
let constraint = all_different(&mut problem, hole);
(Arc::new(problem), vec![constraint])
}
// An exact diagram decides a problem: a solution, or a proof that there is none.
let (problem, constraints) = pigeons(5, 5);
for width in [1, 4, usize::MAX] {
let mut compiler = Compiler::new(
problem.clone(),
CompilationHeuristic::default(),
&constraints,
);
compiler.refine(width, usize::MAX);
let mdd = compiler.mdd();
// `get_solution` returns a solution only if the diagram holds a path of exact nodes, so
// `None` proves nothing, unless the diagram is unsatisfiable.
println!(
"5 pigeons, 5 holes, width {width}: unsat={}, solution={:?}",
mdd.is_unsat(),
mdd.get_solution()
);
}
// Even a relaxed diagram can prove that a problem has no solution.
let (problem, constraints) = pigeons(5, 4);
let mut compiler = Compiler::new(problem, CompilationHeuristic::default(), &constraints);
compiler.refine(1, usize::MAX);
println!(
"5 pigeons, 4 holes, width 1: unsat = {}",
compiler.mdd().is_unsat()
);