use crate::mdd::{Compiler, EdgeIndex, NodeIndex};
use crate::modelling::{Problem, VariableIndex};
fn edge_probability(compiler: &Compiler, probabilities: &[Vec<f64>], edge: EdgeIndex) -> f64 {
let mdd = compiler.mdd();
let variable = mdd.decision_at_layer(edge.0);
probabilities[variable.0][mdd[edge].assignment().0]
}
#[derive(Clone, Debug)]
pub enum MergeHeuristic {
LessRelaxed,
MostLikely(Vec<Vec<f64>>),
StateSimilarity,
}
impl Default for MergeHeuristic {
fn default() -> Self {
Self::StateSimilarity
}
}
const PROBABILITY_SUM_TOLERANCE: f64 = 1e-6;
fn check_probabilities(domain_size: usize, probabilities: &[f64]) {
if probabilities.len() != domain_size {
panic!(
"invalid probabilities: {} probabilities were given for a domain of {domain_size} values",
probabilities.len()
);
}
for (index, &p) in probabilities.iter().enumerate() {
if !p.is_finite() || p < 0.0 {
panic!(
"invalid probabilities: the probability of the value at index {index} is {p}, but probabilities must be finite and non-negative"
);
}
}
let sum: f64 = probabilities.iter().sum();
if (sum - 1.0).abs() > PROBABILITY_SUM_TOLERANCE {
panic!("invalid probabilities: they sum to {sum}, but they must sum to 1");
}
}
impl MergeHeuristic {
pub(crate) fn check(&self, problem: &Problem) {
let Self::MostLikely(probabilities) = self else {
return;
};
assert_eq!(
probabilities.len(),
problem.number_variables(),
"MostLikely needs one row of probabilities per variable of the problem"
);
for (variable, row) in probabilities.iter().enumerate() {
check_probabilities(problem[VariableIndex(variable)].domain_size(), row);
}
}
fn rank_nodes(&self, compiler: &Compiler, layer: usize) -> Vec<NodeIndex> {
let mdd = compiler.mdd();
let active_nodes = || {
(0..mdd.number_nodes_in_layer(layer))
.map(move |position| NodeIndex(layer, position))
.filter(|&node| mdd[node].is_active())
};
match self {
Self::LessRelaxed => rank_by_score(active_nodes().map(|node| {
let parents = mdd[node].number_parents() as f64;
let exact_parents = mdd[node]
.iter_parents()
.map(|edge| mdd[edge].from())
.filter(|&parent| !mdd[parent].is_relaxed())
.count() as f64;
(exact_parents / parents, node)
})),
Self::MostLikely(probabilities) => rank_by_score(active_nodes().map(|node| {
let parents = mdd[node].number_parents() as f64;
let probability_mass: f64 = mdd[node]
.iter_parents()
.map(|edge| edge_probability(compiler, probabilities, edge))
.sum();
(probability_mass / parents, node)
})),
Self::StateSimilarity => {
let mut keyed: Vec<(Vec<f64>, NodeIndex)> = active_nodes()
.map(|node| {
let key = compiler
.top_down_properties(node)
.iter()
.zip(compiler.bottom_up_properties(node))
.flat_map(|(top_down, bottom_up)| {
top_down
.order_key()
.into_iter()
.chain(bottom_up.order_key())
})
.collect();
(key, node)
})
.collect();
keyed.sort_unstable_by(|a, b| {
for (x, y) in a.0.iter().zip(b.0.iter()) {
match x.total_cmp(y) {
std::cmp::Ordering::Equal => continue,
other => return other,
}
}
std::cmp::Ordering::Equal
});
keyed.into_iter().map(|(_, node)| node).collect()
}
}
}
pub(crate) fn group_nodes(
&self,
compiler: &Compiler,
layer: usize,
max_width: usize,
) -> Vec<Vec<NodeIndex>> {
let mdd = compiler.mdd();
assert!(
max_width >= 1,
"a layer cannot be merged down to a width of 0 nodes"
);
let active_nodes = mdd
.nodes_in_layer(layer)
.filter(|&node| mdd[node].is_active())
.count();
assert!(
active_nodes > max_width,
"layer {layer} has {active_nodes} active nodes, which fits the width of {max_width}: \
there is nothing to merge"
);
consecutive_runs(&self.rank_nodes(compiler, layer), max_width)
}
}
fn consecutive_runs(ranking: &[NodeIndex], max_width: usize) -> Vec<Vec<NodeIndex>> {
let nodes = ranking.len();
debug_assert!(nodes > max_width && max_width >= 1);
let (size, larger) = (nodes / max_width, nodes % max_width);
let mut groups = Vec::with_capacity(max_width);
let mut start = 0;
for run in 0..max_width {
let end = start + size + usize::from(run >= max_width - larger);
groups.push(ranking[start..end].to_vec());
start = end;
}
groups
}
fn rank_by_score(scored: impl Iterator<Item = (f64, NodeIndex)>) -> Vec<NodeIndex> {
let mut scored: Vec<(f64, NodeIndex)> = scored.collect();
scored.sort_unstable_by(|a, b| a.0.total_cmp(&b.0));
scored.into_iter().map(|(_, node)| node).collect()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::constraints::{all_different, gcc};
use crate::mdd::Compiler;
use crate::mdd::heuristics::{CompilationHeuristic, OrderingHeuristic, SelectHeuristic};
use crate::modelling::Problem;
use std::sync::Arc;
fn all() -> [MergeHeuristic; 3] {
[
MergeHeuristic::LessRelaxed,
MergeHeuristic::MostLikely(vec![vec![0.1, 0.2, 0.3, 0.1, 0.3]; 5]),
MergeHeuristic::StateSimilarity,
]
}
fn nodes(count: usize) -> Vec<NodeIndex> {
(0..count).map(|i| NodeIndex(1, i)).collect()
}
#[test]
#[should_panic(expected = "there is nothing to merge")]
fn a_layer_that_fits_is_not_ranked() {
let compiler = exact_mdd(MergeHeuristic::LessRelaxed);
let mdd = compiler.mdd();
let active = mdd
.nodes_in_layer(2)
.filter(|&n| mdd[n].is_active())
.count();
MergeHeuristic::LessRelaxed.group_nodes(&compiler, 2, active);
}
#[test]
fn runs_are_consecutive_and_the_larger_ones_come_last() {
let ranking = nodes(7);
assert_eq!(
consecutive_runs(&ranking, 3),
vec![
vec![ranking[0], ranking[1]],
vec![ranking[2], ranking[3]],
vec![ranking[4], ranking[5], ranking[6]],
]
);
}
#[test]
fn a_width_of_one_merges_everything_into_one_node() {
let ranking = nodes(5);
assert_eq!(consecutive_runs(&ranking, 1), vec![ranking]);
}
#[test]
fn the_runs_partition_the_ranking_in_order_and_differ_by_at_most_one() {
for count in 2..=14 {
for width in 1..count {
let ranking = nodes(count);
let runs = consecutive_runs(&ranking, width);
assert_eq!(runs.len(), width, "{count}/{width}");
assert_eq!(runs.concat(), ranking, "{count}/{width}");
let (smallest, largest) = runs
.iter()
.map(Vec::len)
.fold((usize::MAX, 0), |(lo, hi), len| (lo.min(len), hi.max(len)));
assert!(largest - smallest <= 1, "{count}/{width}");
}
}
}
#[test]
#[should_panic(expected = "width of 0 nodes")]
fn merging_down_to_no_node_is_refused() {
let compiler = exact_mdd(MergeHeuristic::LessRelaxed);
MergeHeuristic::LessRelaxed.group_nodes(&compiler, 1, 0);
}
fn exact_mdd_unrefined(heuristic: MergeHeuristic) -> Compiler {
let mut problem = Problem::default();
let vars = problem.add_variables(5, vec![0, 1, 2, 3, 4]);
let all_different = all_different(&mut problem, vars.clone());
let counted = gcc(&mut problem, vars, vec![(0, 0, 2), (1, 0, 2)]);
Compiler::new(
Arc::new(problem),
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: heuristic,
selection: SelectHeuristic::Greedy,
},
&[all_different, counted],
)
}
fn exact_mdd(heuristic: MergeHeuristic) -> Compiler {
let mut compiler = exact_mdd_unrefined(heuristic.clone());
compiler.refine(usize::MAX);
let mdd = compiler.mdd();
assert!(!mdd.is_unsat() && mdd.count_solutions() > 0u32.into());
compiler
}
#[test]
fn the_groups_partition_the_active_nodes_of_the_layer() {
for heuristic in all() {
let compiler = exact_mdd(heuristic.clone());
let mdd = compiler.mdd();
for layer in 1..mdd.number_layers() - 1 {
let active: Vec<_> = mdd
.nodes_in_layer(layer)
.filter(|&n| mdd[n].is_active())
.collect();
for width in [1, 2, active.len().saturating_sub(1).max(1)] {
if active.len() <= width {
continue;
}
let groups = heuristic.group_nodes(&compiler, layer, width);
assert_eq!(groups.len(), width, "{heuristic:?} layer {layer}");
let mut merged = groups.concat();
merged.sort();
assert_eq!(merged, active, "{heuristic:?} layer {layer} width {width}");
}
}
}
}
#[test]
fn a_relaxation_keeps_the_width_and_every_solution_whatever_the_heuristic() {
let exact: u64 = exact_mdd(MergeHeuristic::LessRelaxed)
.mdd()
.count_solutions()
.try_into()
.unwrap();
for heuristic in all() {
for width in [1, 2, 3, 6] {
let mut compiler = exact_mdd_unrefined(heuristic.clone());
compiler.refine(width);
let mdd = compiler.mdd();
assert!(
(0..mdd.number_layers()).all(|l| mdd.number_nodes_in_layer(l) <= width),
"{heuristic:?} width {width}"
);
let relaxed: u64 = mdd.count_solutions().try_into().unwrap();
assert!(relaxed >= exact, "{heuristic:?} width {width}");
}
}
}
#[test]
fn a_ranking_lists_each_active_node_of_the_layer_once() {
for heuristic in all() {
let compiler = exact_mdd(heuristic.clone());
let mdd = compiler.mdd();
for layer in 0..mdd.number_layers() {
let mut ranking = heuristic.rank_nodes(&compiler, layer);
ranking.sort();
let active: Vec<_> = mdd
.nodes_in_layer(layer)
.filter(|&n| mdd[n].is_active())
.collect();
assert_eq!(ranking, active, "{heuristic:?} layer {layer}");
}
}
}
}