use std::collections::HashMap;
use std::sync::Arc;
use indicatif::{ParallelProgressIterator, ProgressBar, ProgressStyle};
use rand::SeedableRng;
use rand::rngs::StdRng;
use rayon::prelude::*;
use crate::bp::belief_propagation;
use crate::mdd::arena::{MddCompilationConfig, compile_constraints};
use crate::mdd::{CompiledConstraint, MddArena};
use crate::modelling::{Problem, ValueIndex, VariableIndex};
use crate::sampling::{DecodeMode, argmax, sample_categorical_with};
pub type Compiled = Arc<Vec<CompiledConstraint>>;
pub struct MddRepair {
compilation: MddCompilationConfig,
domain_size: usize,
mode: DecodeMode,
bp_iterations: usize,
}
impl MddRepair {
pub fn new(
compilation: MddCompilationConfig,
domain_size: usize,
mode: DecodeMode,
bp_iterations: usize,
) -> Self {
Self {
compilation,
domain_size,
mode,
bp_iterations,
}
}
pub fn domain_size_covering(problems: &[Arc<Problem>]) -> usize {
problems
.iter()
.flat_map(|problem| {
problem
.iter_variables()
.flat_map(|v| problem[v].iter_domain().collect::<Vec<_>>())
})
.map(|value| value as usize + 1)
.max()
.unwrap_or(1)
}
const PROGRESS_BAR_MIN_PROBLEMS: usize = 4;
pub fn prepare(&self, problems: &[Arc<Problem>]) -> Vec<Compiled> {
let arena = MddArena::new();
let mut first_of: HashMap<usize, usize> = HashMap::new();
let mut unique: Vec<&Arc<Problem>> = Vec::new();
let slots: Vec<usize> = problems
.iter()
.map(|problem| {
*first_of
.entry(Arc::as_ptr(problem) as usize)
.or_insert_with(|| {
unique.push(problem);
unique.len() - 1
})
})
.collect();
let compile = |problem: &&Arc<Problem>| {
Arc::new(compile_constraints(
problem,
&arena,
&self.compilation,
self.domain_size,
))
};
let compiled: Vec<Arc<Vec<CompiledConstraint>>> =
if unique.len() < Self::PROGRESS_BAR_MIN_PROBLEMS {
crate::utils::worker_pool().install(|| unique.par_iter().map(compile).collect())
} else {
let progress = ProgressBar::new(unique.len() as u64);
progress.set_style(
ProgressStyle::with_template(
"{msg} [{elapsed_precise}] [{bar:40.cyan/blue}] {pos}/{len} ({eta})",
)
.expect("hard-coded progress bar template should always be valid"),
);
progress.set_message("Compiling MDDs");
let compiled = crate::utils::worker_pool().install(|| {
unique
.par_iter()
.progress_with(progress.clone())
.map(compile)
.collect()
});
progress.finish_and_clear();
compiled
};
slots
.into_iter()
.map(|slot| Arc::clone(&compiled[slot]))
.collect()
}
pub fn repair(
&self,
problem: &Problem,
compiled: Option<&Compiled>,
current: &[isize],
free: &[usize],
rng: &mut StdRng,
probability: impl Fn(usize, usize) -> f64,
) -> Vec<isize> {
if free.is_empty() {
return current.to_vec();
}
let compiled =
compiled.expect("the MDD repair needs its problems prepared before it repairs them");
let n = current.len();
let domain_width = self.domain_size;
let mut assignment = vec![ValueIndex(0); n];
let mut decided = vec![true; n];
for &v in free {
decided[v] = false;
}
let mut probs: Vec<Vec<f64>> = Vec::with_capacity(n);
for v in 0..n {
let variable = VariableIndex(v);
assignment[v] = ValueIndex(current[v] as usize);
let probs_v: Vec<f64> = (0..domain_width)
.map(|raw_value| {
if problem[variable].in_domain(raw_value as isize) {
probability(v, raw_value)
} else {
0.0
}
})
.collect();
probs.push(probs_v);
}
let marginals =
belief_propagation(compiled, &probs, &assignment, &decided, self.bp_iterations);
let mut next = current.to_vec();
for &v in free {
let chosen = match self.mode {
DecodeMode::Greedy => argmax(&marginals[v]),
DecodeMode::Sample => sample_categorical_with(&marginals[v], rng),
};
next[v] = chosen as isize;
}
next
}
}
pub struct BatchRepair {
repair: MddRepair,
compiled: Vec<Option<Compiled>>,
}
impl BatchRepair {
pub fn new(repair: MddRepair, problems: &[Arc<Problem>]) -> Self {
let compiled = repair.prepare(problems).into_iter().map(Some).collect();
Self { repair, compiled }
}
pub fn repair_rows(
&self,
problems: &[Arc<Problem>],
assignments: &mut [Vec<isize>],
destroyed: &[Vec<usize>],
seeds: &[u64],
probability: impl Fn(usize, usize, usize) -> f64 + Sync,
) {
let next: Vec<Vec<isize>> = crate::utils::worker_pool().install(|| {
(0..problems.len())
.into_par_iter()
.map(|row| {
let mut rng = StdRng::seed_from_u64(seeds[row]);
self.repair.repair(
&problems[row],
self.compiled[row].as_ref(),
&assignments[row],
&destroyed[row],
&mut rng,
|variable, value| probability(row, variable, value),
)
})
.collect()
});
for (row, values) in assignments.iter_mut().zip(next) {
*row = values;
}
}
pub fn solved(&mut self, solved: &[bool]) {
for (compiled, &is_solved) in self.compiled.iter_mut().zip(solved) {
if is_solved {
*compiled = None;
}
}
}
pub fn retain(&mut self, keep: &[bool]) {
self.compiled = super::filtered(std::mem::take(&mut self.compiled), keep);
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::constraints::all_different;
use rand::SeedableRng;
fn clique_problem(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)
}
fn repairer(domain_size: usize) -> MddRepair {
MddRepair::new(
MddCompilationConfig::default(),
domain_size,
DecodeMode::Greedy,
1,
)
}
#[test]
fn prepare_returns_one_state_per_problem_in_order() {
let problems = vec![clique_problem(3, 3), clique_problem(4, 4)];
let compiled = repairer(4).prepare(&problems);
assert_eq!(compiled.len(), 2);
assert_eq!(compiled[0].len(), 1);
assert_eq!(compiled[1][0].number_decisions(), 4);
}
#[test]
fn prepare_compiles_each_distinct_problem_once_even_with_duplicates() {
let a = clique_problem(6, 5);
let b = clique_problem(4, 4);
let compiled = repairer(5).prepare(&[a.clone(), a.clone(), a.clone(), b.clone()]);
assert!(Arc::ptr_eq(&compiled[0], &compiled[1]));
assert!(Arc::ptr_eq(&compiled[0], &compiled[2]));
assert!(!Arc::ptr_eq(&compiled[0], &compiled[3]));
}
#[test]
fn covering_domain_size_is_the_largest_value_plus_one() {
let problems = vec![clique_problem(2, 2), clique_problem(2, 5)];
assert_eq!(MddRepair::domain_size_covering(&problems), 5);
}
#[test]
fn repair_changes_only_the_free_positions_and_stays_in_the_domain() {
let problems = vec![clique_problem(3, 3)];
let repairer = repairer(3);
let compiled = repairer.prepare(&problems);
let next = repairer.repair(
&problems[0],
Some(&compiled[0]),
&[0, 1, 2],
&[0],
&mut StdRng::seed_from_u64(0),
|_, _| 1.0 / 3.0,
);
assert_eq!(next[1..], [1, 2]);
assert!((0..3).contains(&next[0]));
}
#[test]
fn a_row_without_free_position_is_kept_and_needs_no_compiled_state() {
let problem = clique_problem(3, 3);
let next = repairer(3).repair(
&problem,
None,
&[2, 1, 0],
&[],
&mut StdRng::seed_from_u64(0),
|_, _| 0.0,
);
assert_eq!(next, [2, 1, 0]);
}
}