use std::sync::Arc;
use rand::rngs::StdRng;
use crate::destroy::{DestroyKind, DestroyOperator};
use crate::mdd::arena::MddCompilationConfig;
use crate::modelling::Problem;
use crate::sampling::DecodeMode;
use super::repair::{BatchRepair, MddRepair};
use super::{SearchArchitecture, SearchState, destroy_rows, row_seeds};
#[derive(Debug, Clone)]
pub struct BeliefPropagationSearchConfig {
pub destroy_kind: DestroyKind,
pub destroy_fraction: f64,
pub stochastic: bool,
pub bp_iterations: usize,
}
impl Default for BeliefPropagationSearchConfig {
fn default() -> Self {
Self {
destroy_kind: DestroyKind::default(),
destroy_fraction: 1.0,
stochastic: true,
bp_iterations: 1,
}
}
}
pub struct BeliefPropagationSearch {
destroy_op: Box<dyn DestroyOperator>,
mode: DecodeMode,
bp_iterations: usize,
}
impl BeliefPropagationSearch {
pub fn new(config: &BeliefPropagationSearchConfig) -> Self {
Self {
destroy_op: config.destroy_kind.build(config.destroy_fraction),
mode: if config.stochastic {
DecodeMode::Sample
} else {
DecodeMode::Greedy
},
bp_iterations: config.bp_iterations,
}
}
}
impl SearchArchitecture for BeliefPropagationSearch {
fn setup<'a>(&'a self, problems: &[Arc<Problem>]) -> Result<Box<dyn SearchState + 'a>, String> {
let domain_size = MddRepair::domain_size_covering(problems);
let repair = MddRepair::new(
MddCompilationConfig::default(),
domain_size,
self.mode,
self.bp_iterations,
);
Ok(Box::new(BeliefPropagationState {
search: self,
repair: BatchRepair::new(repair, problems),
uniform: 1.0 / domain_size as f64,
}))
}
}
struct BeliefPropagationState<'a> {
search: &'a BeliefPropagationSearch,
repair: BatchRepair,
uniform: f64,
}
impl SearchState for BeliefPropagationState<'_> {
fn step(
&mut self,
problems: &[Arc<Problem>],
assignments: &mut [Vec<isize>],
pending: &[bool],
rng: &mut StdRng,
) {
let destroyed = destroy_rows(
self.search.destroy_op.as_ref(),
problems,
assignments,
pending,
rng,
);
let seeds = row_seeds(problems.len(), rng);
let uniform = self.uniform;
self.repair
.repair_rows(problems, assignments, &destroyed, &seeds, |_, _, _| uniform);
}
fn solved(&mut self, solved: &[bool]) {
self.repair.solved(solved);
}
fn retain(&mut self, keep: &[bool]) {
self.repair.retain(keep);
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::constraints::all_different;
use crate::local_search::{Budget, LocalSearch};
fn clique(size: usize, colours: usize) -> Arc<Problem> {
let mut problem = Problem::default();
let vars = problem.add_variables(size, (0..colours as isize).collect());
all_different(&mut problem, vars);
Arc::new(problem)
}
#[test]
fn problems_of_different_sizes_are_solved_together() {
let problems = vec![clique(3, 3), clique(5, 6), clique(4, 4)];
let search = LocalSearch::new(Box::new(BeliefPropagationSearch::new(
&BeliefPropagationSearchConfig {
destroy_fraction: 0.5,
stochastic: true,
bp_iterations: 3,
..BeliefPropagationSearchConfig::default()
},
)));
let budget = Budget {
iteration_limit: 2000,
..Budget::default()
};
let solutions = search.run(&problems, budget, 0, None).unwrap();
for (problem, solution) in problems.iter().zip(&solutions) {
let values = solution.assignment().expect("an easy problem is solved");
assert!(problem.is_solution(values));
}
}
}