use super::{Mdd, NodeIndex};
struct Scaled {
alpha: Vec<Vec<f64>>,
beta: Vec<Vec<f64>>,
scale: Vec<f64>,
}
impl Scaled {
fn log_wmc(&self) -> f64 {
self.scale.iter().map(|c| c.ln()).sum()
}
}
fn assert_well_formed(mdd: &Mdd) {
let last_layer = mdd.sink().0;
assert_eq!(
last_layer + 1,
mdd.number_layers(),
"the sink is in layer {last_layer} but the diagram has {} layers: the sink must be in the \
last one",
mdd.number_layers()
);
assert_eq!(
mdd.number_nodes_in_layer(0),
1,
"the root layer must have exactly one node"
);
assert_eq!(
mdd.number_nodes_in_layer(last_layer),
1,
"the sink layer must have exactly one node"
);
assert_eq!(
mdd.root(),
NodeIndex(0, 0),
"the root must be node 0 of layer 0"
);
assert_eq!(
mdd.sink(),
NodeIndex(last_layer, 0),
"the sink must be node 0 of the last layer"
);
for layer in 0..last_layer {
for node in mdd.nodes_in_layer(layer) {
for edge in mdd[node].iter_children() {
assert!(
mdd[edge].is_active(),
"node {node:?} lists the deactivated edge {edge:?}: the diagram was not cleaned"
);
assert_eq!(
mdd[edge].to().0,
layer + 1,
"edge {edge:?} leaves layer {layer} but does not enter layer {}",
layer + 1
);
}
}
}
}
fn scaled_forward_backward(mdd: &Mdd, weights: &[Vec<f64>]) -> Scaled {
if cfg!(debug_assertions) {
assert_well_formed(mdd);
}
let last_layer = mdd.sink().0;
if last_layer != weights.len() {
panic!(
"Calling the passes on an MDD structure with {} layers and {} layer's weights",
last_layer,
weights.len()
);
}
let mut alpha: Vec<Vec<f64>> = Vec::with_capacity(last_layer + 1);
let mut scale = vec![1.0];
alpha.push(vec![1.0]);
for layer in 0..last_layer {
let mut next_alpha = vec![0.0; mdd.number_nodes_in_layer(layer + 1)];
for node in mdd.nodes_in_layer(layer) {
let mass = alpha[layer][node.1];
if mass == 0.0 {
continue;
}
for edge in mdd[node].iter_children() {
let value = mdd[edge].assignment();
let weight = weights[layer][value.0];
next_alpha[mdd[edge].to().1] += mass * weight;
}
}
let total: f64 = next_alpha.iter().sum();
if total > 0.0 {
for mass in &mut next_alpha {
*mass /= total;
}
}
scale.push(total);
alpha.push(next_alpha);
}
let mut beta: Vec<Vec<f64>> = vec![Vec::new(); last_layer + 1];
beta[last_layer] = vec![1.0];
for layer in (0..last_layer).rev() {
let mut layer_beta = vec![0.0; mdd.number_nodes_in_layer(layer)];
if scale[layer + 1] > 0.0 {
for node in mdd.nodes_in_layer(layer) {
let mut mass = 0.0;
for edge in mdd[node].iter_children() {
let value = mdd[edge].assignment();
let weight = weights[layer][value.0];
mass += weight * beta[layer + 1][mdd[edge].to().1];
}
layer_beta[node.1] = mass / scale[layer + 1];
}
}
beta[layer] = layer_beta;
}
Scaled { alpha, beta, scale }
}
pub fn log_wmc(mdd: &Mdd, weights: &[Vec<f64>]) -> f64 {
if mdd.is_unsat() {
return f64::NEG_INFINITY;
}
scaled_forward_backward(mdd, weights).log_wmc()
}
pub fn wmc(mdd: &Mdd, weights: &[Vec<f64>]) -> f64 {
log_wmc(mdd, weights).exp()
}
pub fn log_wmc_and_gradient(mdd: &Mdd, weights: &[Vec<f64>]) -> (f64, Vec<Vec<f64>>) {
let mut gradient: Vec<Vec<f64>> = weights.iter().map(|row| vec![0.0; row.len()]).collect();
if mdd.is_unsat() {
return (f64::NEG_INFINITY, gradient);
}
let scaled = scaled_forward_backward(mdd, weights);
let log_count = scaled.log_wmc();
let last_layer = mdd.sink().0;
if log_count == f64::NEG_INFINITY {
return (log_count, gradient);
}
for (layer, row) in gradient.iter_mut().enumerate().take(last_layer) {
let factor = 1.0 / scaled.scale[layer + 1];
for node in mdd.nodes_in_layer(layer) {
let alpha = scaled.alpha[layer][node.1];
if alpha == 0.0 {
continue;
}
for edge in mdd[node].iter_children() {
let value = mdd[edge].assignment();
row[value.0] += factor * alpha * scaled.beta[layer + 1][mdd[edge].to().1];
}
}
}
(log_count, gradient)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::constraints::{all_different, not_equals, sum};
use crate::mdd::arena::{MddArena, compile_constraint, nominal_domain};
use crate::mdd::heuristics::{
CompilationHeuristic, MergeHeuristic, OrderingHeuristic, SelectHeuristic,
};
use crate::mdd::{Compiler, Mdd};
use crate::mdd::{Edge, EdgeIndex, Node};
use crate::modelling::{ConstraintIndex, Problem, ValueIndex};
use std::sync::Arc;
fn build_mdd(problem: Arc<Problem>, constraints: &[ConstraintIndex]) -> Mdd {
let mut compiler = Compiler::new(
problem,
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::LessRelaxed,
selection: SelectHeuristic::Greedy,
},
constraints,
);
compiler.refine(usize::MAX);
compiler.into_mdd()
}
fn brute_force(
problem: &Problem,
weights: &[Vec<f64>],
decided: &[bool],
assignment: &[ValueIndex],
) -> f64 {
let mut total = 0.0;
let mut tuple = vec![0isize; problem.number_variables()];
loop {
let agrees =
(0..tuple.len()).all(|v| !decided[v] || assignment[v].0 as isize == tuple[v]);
if agrees && problem.is_solution(&tuple) {
total += (0..tuple.len())
.map(|v| weights[v][tuple[v] as usize])
.product::<f64>();
}
let mut position = 0;
loop {
if position == tuple.len() {
return total;
}
tuple[position] += 1;
if (tuple[position] as usize) < weights[position].len() {
break;
}
tuple[position] = 0;
position += 1;
}
}
}
fn by_layer(mdd: &Mdd, by_variable: &[Vec<f64>]) -> Vec<Vec<f64>> {
(0..mdd.number_layers() - 1)
.map(|layer| by_variable[mdd.decision_at_layer(layer).0].clone())
.collect()
}
fn some_weights(variables: usize, domain: usize) -> Vec<Vec<f64>> {
(0..variables)
.map(|v| {
(0..domain)
.map(|d| 0.1 + 0.07 * ((3 * v + 5 * d) % 11) as f64)
.collect()
})
.collect()
}
fn brute_force_not_equals(probs: &[f64], domain_size: usize) -> f64 {
let mut brute = 0.0;
for a in 0..domain_size {
for b in 0..domain_size {
if a != b {
brute += probs[a] * probs[domain_size + b];
}
}
}
brute
}
fn chain(layers: usize, values: usize) -> Mdd {
let nodes = (0..=layers)
.map(|layer| vec![Node::new(layer, 0, false)])
.collect();
let mut diagram = Mdd::from_parts(nodes, vec![Vec::new(); layers]);
for layer in 0..layers {
for value in 0..values {
add_edge(
&mut diagram,
layer,
NodeIndex(layer, 0),
NodeIndex(layer + 1, 0),
value,
);
}
}
diagram
}
fn add_edge(diagram: &mut Mdd, layer: usize, from: NodeIndex, to: NodeIndex, value: usize) {
let index = EdgeIndex(layer, diagram.edges[layer].len());
diagram.edges[layer].push(Edge::new(from, to, ValueIndex(value)));
diagram.nodes[from.0][from.1].add_child_edge(index);
}
fn add_node(diagram: &mut Mdd, layer: usize) {
let index = diagram.nodes[layer].len();
diagram.nodes[layer].push(Node::new(layer, index, false));
}
#[test]
fn wmc_matches_brute_force_for_not_equals() {
let mut problem = Problem::default();
let x = problem.add_variable(vec![0, 1, 2]);
let y = problem.add_variable(vec![0, 1, 2]);
not_equals(&mut problem, x, y);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mdd = build_mdd(problem, &constraints);
let weights = vec![vec![0.2, 0.5, 0.3], vec![0.1, 0.3, 0.6]];
let expected = brute_force_not_equals(&weights.concat(), 3);
assert!((wmc(&mdd, &weights) - expected).abs() < 1e-9);
assert!((log_wmc(&mdd, &weights) - expected.ln()).abs() < 1e-9);
}
#[test]
fn unit_weights_count_the_solutions() {
let mut problem = Problem::default();
let vars = problem.add_variables(4, vec![0, 1, 2, 3]);
all_different(&mut problem, vars);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mdd = build_mdd(problem, &constraints);
assert!((wmc(&mdd, &vec![vec![1.0; 4]; 4]) - 24.0).abs() < 1e-9);
assert_eq!(mdd.count_solutions().to_string(), "24");
}
#[test]
fn wmc_matches_brute_force_on_several_constraints() {
let mut problem = Problem::default();
let vars = problem.add_variables(4, vec![0, 1, 2]);
all_different(&mut problem, vars[..3].to_vec());
not_equals(&mut problem, vars[2], vars[3]);
sum(&mut problem, vars.clone(), 4);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mdd = build_mdd(Arc::clone(&problem), &constraints);
let weights = some_weights(4, 3);
let expected = brute_force(&problem, &weights, &[false; 4], &[ValueIndex(0); 4]);
assert!(expected > 0.0);
assert!((wmc(&mdd, &by_layer(&mdd, &weights)) - expected).abs() < 1e-9);
}
#[test]
fn an_unsatisfiable_diagram_has_no_weight_and_no_gradient() {
let mut problem = Problem::default();
let vars = problem.add_variables(3, vec![0, 1]);
all_different(&mut problem, vars);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mdd = build_mdd(problem, &constraints);
assert!(mdd.is_unsat());
let weights = vec![vec![0.5, 0.5]; 3];
let (log_count, gradient) = log_wmc_and_gradient(&mdd, &weights);
assert_eq!(log_count, f64::NEG_INFINITY);
assert_eq!(wmc(&mdd, &weights), 0.0);
assert_eq!(gradient, vec![vec![0.0; 2]; 3]);
}
#[test]
fn weights_that_forbid_every_solution_give_a_zero_count() {
let mut problem = Problem::default();
let vars = problem.add_variables(2, vec![0, 1]);
not_equals(&mut problem, vars[0], vars[1]);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mdd = build_mdd(Arc::clone(&problem), &constraints);
let by_variable = vec![vec![1.0, 0.0], vec![1.0, 0.0]];
let weights = by_layer(&mdd, &by_variable);
let (log_count, gradient) = log_wmc_and_gradient(&mdd, &weights);
assert_eq!(log_count, f64::NEG_INFINITY);
assert_eq!(gradient, vec![vec![0.0; 2]; 2]);
}
#[test]
fn the_scaled_passes_meet_at_every_layer() {
let mut problem = Problem::default();
let vars = problem.add_variables(4, vec![0, 1, 2]);
all_different(&mut problem, vars[..3].to_vec());
sum(&mut problem, vars.clone(), 4);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mdd = build_mdd(problem, &constraints);
let weights = by_layer(&mdd, &some_weights(4, 3));
let scaled = scaled_forward_backward(&mdd, &weights);
assert!(scaled.log_wmc() > f64::NEG_INFINITY);
for layer in 0..mdd.number_layers() {
let through: f64 = scaled.alpha[layer]
.iter()
.zip(&scaled.beta[layer])
.map(|(a, b)| a * b)
.sum();
assert!((through - 1.0).abs() < 1e-9, "layer {layer}: {through}");
assert!((scaled.alpha[layer].iter().sum::<f64>() - 1.0).abs() < 1e-9);
}
}
#[test]
fn gradient_is_the_derivative_of_the_log_count() {
let mut problem = Problem::default();
let vars = problem.add_variables(3, vec![0, 1, 2]);
all_different(&mut problem, vars.clone());
not_equals(&mut problem, vars[0], vars[1]);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mdd = build_mdd(problem, &constraints);
let weights = vec![
vec![0.2, 0.5, 0.3],
vec![0.1, 0.3, 0.6],
vec![0.4, 0.4, 0.2],
];
let (log_count, grad) = log_wmc_and_gradient(&mdd, &weights);
assert!((log_wmc(&mdd, &weights) - log_count).abs() < 1e-12);
assert_eq!(grad.len(), weights.len());
let eps = 1e-6;
for layer in 0..weights.len() {
for value in 0..weights[layer].len() {
let mut bumped = weights.clone();
bumped[layer][value] += eps;
let finite_diff = (log_wmc(&mdd, &bumped) - log_count) / eps;
assert!(
(finite_diff - grad[layer][value]).abs() < 1e-4,
"layer={layer} value={value} analytic={} finite_diff={finite_diff}",
grad[layer][value],
);
}
}
}
#[test]
fn gradient_times_the_weight_is_the_probability_of_the_value() {
let mut problem = Problem::default();
let vars = problem.add_variables(3, vec![0, 1, 2]);
all_different(&mut problem, vars.clone());
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mdd = build_mdd(Arc::clone(&problem), &constraints);
let by_variable = some_weights(3, 3);
let weights = by_layer(&mdd, &by_variable);
let (_, grad) = log_wmc_and_gradient(&mdd, &weights);
let total = brute_force(&problem, &by_variable, &[false; 3], &[ValueIndex(0); 3]);
for layer in 0..3 {
let variable = mdd.decision_at_layer(layer).0;
let mut layer_sum = 0.0;
for value in 0..3 {
let mut decided = [false; 3];
decided[variable] = true;
let mut assignment = [ValueIndex(0); 3];
assignment[variable] = ValueIndex(value);
let joint = brute_force(&problem, &by_variable, &decided, &assignment);
let probability = weights[layer][value] * grad[layer][value];
assert!((probability - joint / total).abs() < 1e-9);
layer_sum += probability;
}
assert!((layer_sum - 1.0).abs() < 1e-9);
}
}
#[test]
fn a_structure_shared_through_the_arena_counts_with_its_own_order() {
let mut problem = Problem::default();
let vars = problem.add_variables(4, vec![0, 1, 2]);
let constraint = sum(&mut problem, vec![vars[3], vars[1], vars[0], vars[2]], 5);
let problem = Arc::new(problem);
let compiled = compile_constraint(
&MddArena::new(),
&problem,
constraint,
&OrderingHeuristic::MinDomMaxLinked,
&nominal_domain(3),
usize::MAX,
);
let weights = some_weights(4, 3);
let expected = brute_force(&problem, &weights, &[false; 4], &[ValueIndex(0); 4]);
assert!(expected > 0.0);
let by_layer: Vec<Vec<f64>> = (0..compiled.order.len())
.map(|layer| weights[compiled.order[layer].0].clone())
.collect();
assert!((wmc(&compiled, &by_layer) - expected).abs() < 1e-9);
}
#[test]
fn a_count_below_the_smallest_float_is_still_known_through_its_logarithm() {
let diagram = chain(400, 2);
let weights = vec![vec![1e-3, 1e-3]; 400];
let (log_count, gradient) = log_wmc_and_gradient(&diagram, &weights);
assert!((log_count - 400.0 * 0.002f64.ln()).abs() < 1e-9);
assert_eq!(wmc(&diagram, &weights), 0.0);
for row in &gradient {
for &g in row {
assert!((g - 500.0).abs() < 1e-6, "{g}");
}
}
}
#[test]
#[should_panic(expected = "layer's weights")]
fn too_few_rows_of_weights_are_reported() {
let mut problem = Problem::default();
let vars = problem.add_variables(3, vec![0, 1, 2]);
all_different(&mut problem, vars);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mdd = build_mdd(problem, &constraints);
wmc(&mdd, &[vec![1.0; 3], vec![1.0; 3]]);
}
#[test]
fn a_hand_built_chain_is_well_formed() {
let diagram = chain(3, 2);
assert_well_formed(&diagram);
assert!((wmc(&diagram, &vec![vec![1.0, 1.0]; 3]) - 8.0).abs() < 1e-9);
}
#[test]
#[cfg(debug_assertions)]
#[should_panic(expected = "root layer must have exactly one node")]
fn a_second_root_is_reported() {
let mut diagram = chain(2, 2);
add_node(&mut diagram, 0);
assert_well_formed(&diagram);
}
#[test]
#[cfg(debug_assertions)]
#[should_panic(expected = "sink layer must have exactly one node")]
fn a_second_sink_is_reported() {
let mut diagram = chain(2, 2);
add_node(&mut diagram, 2);
assert_well_formed(&diagram);
}
#[test]
#[cfg(debug_assertions)]
#[should_panic(expected = "deactivated edge")]
fn a_listed_deactivated_edge_is_reported() {
let mut diagram = chain(2, 2);
diagram.edges[0][1].deactivate();
assert_well_formed(&diagram);
}
#[test]
#[cfg(debug_assertions)]
#[should_panic(expected = "does not enter layer")]
fn an_edge_that_skips_a_layer_is_reported() {
let mut diagram = chain(3, 1);
add_edge(&mut diagram, 0, NodeIndex(0, 0), NodeIndex(2, 0), 1);
assert_well_formed(&diagram);
}
#[test]
#[cfg(debug_assertions)]
#[should_panic(expected = "root layer must have exactly one node")]
fn the_passes_check_the_diagram_in_debug_builds() {
let mut diagram = chain(2, 2);
add_node(&mut diagram, 0);
wmc(&diagram, &vec![vec![1.0, 1.0]; 2]);
}
}