#![deny(missing_docs)]
#![warn(clippy::missing_docs_in_private_items)]
mod bp_search;
mod config;
#[cfg(feature = "learning")]
mod neural_prior;
pub mod repair;
pub use bp_search::{BeliefPropagationSearch, BeliefPropagationSearchConfig};
pub use config::{Budget, SearchConfig, SolveConfig};
#[cfg(feature = "learning")]
pub use neural_prior::{
NeuralPriorBpSearch, NeuralPriorBpSearchConfig, NeuralPriorSearch, NeuralPriorSearchConfig,
solve_with_network,
};
use std::path::Path;
use std::sync::Arc;
use std::time::Instant;
use indicatif::{ProgressBar, ProgressStyle};
use rand::rngs::StdRng;
use rand::{RngExt, SeedableRng};
use rayon::prelude::*;
use crate::destroy::DestroyOperator;
use crate::modelling::{Problem, Solution, Status};
struct StoppingCriterion {
budget: Budget,
start: Instant,
iters_done: usize,
}
impl StoppingCriterion {
fn new(budget: Budget) -> Self {
Self {
budget,
start: Instant::now(),
iters_done: 0,
}
}
fn tick(&mut self) {
self.iters_done += 1;
}
fn is_exhausted(&self) -> bool {
self.start.elapsed() >= self.budget.time_limit
|| self.iters_done >= self.budget.iteration_limit
}
}
pub trait SearchArchitecture {
fn setup<'a>(&'a self, problems: &[Arc<Problem>]) -> Result<Box<dyn SearchState + 'a>, String>;
}
pub trait SearchState {
fn step(
&mut self,
problems: &[Arc<Problem>],
assignments: &mut [Vec<isize>],
pending: &[bool],
rng: &mut StdRng,
);
fn solved(&mut self, _solved: &[bool]) {}
fn retain(&mut self, _keep: &[bool]) {}
}
fn random_assignments(problems: &[Arc<Problem>], rng: &mut StdRng) -> Vec<Vec<isize>> {
problems
.iter()
.map(|problem| crate::sampling::random_assignment_with(problem, rng))
.collect()
}
pub fn destroy_rows(
destroy_op: &dyn DestroyOperator,
problems: &[Arc<Problem>],
assignments: &[Vec<isize>],
pending: &[bool],
rng: &mut StdRng,
) -> Vec<Vec<usize>> {
let seeds = row_seeds(problems.len(), rng);
crate::utils::worker_pool().install(|| {
assignments
.par_iter()
.zip(problems.par_iter())
.zip(seeds.par_iter())
.zip(pending.par_iter())
.map(|(((row, problem), &seed), &is_pending)| {
if !is_pending {
return Vec::new();
}
let mut rng = StdRng::seed_from_u64(seed);
destroy_op.destroy(problem, row, &mut rng)
})
.collect()
})
}
pub fn row_seeds(rows: usize, rng: &mut StdRng) -> Vec<u64> {
(0..rows).map(|_| rng.random::<u64>()).collect()
}
fn filtered<T>(items: Vec<T>, keep: &[bool]) -> Vec<T> {
items
.into_iter()
.zip(keep)
.filter_map(|(item, &kept)| kept.then_some(item))
.collect()
}
pub struct LocalSearch {
architecture: Box<dyn SearchArchitecture>,
}
impl LocalSearch {
const COMPACTION_INTERVAL: usize = 100;
pub fn new(architecture: Box<dyn SearchArchitecture>) -> Self {
Self { architecture }
}
pub fn run(
&self,
problems: &[Arc<Problem>],
budget: Budget,
seed: u64,
progress: Option<&indicatif::ProgressBar>,
) -> Result<Vec<Solution>, String> {
if problems.is_empty() {
return Ok(Vec::new());
}
let mut rng = StdRng::seed_from_u64(seed);
let mut stop = StoppingCriterion::new(budget);
let mut active: Vec<usize> = (0..problems.len()).collect();
let mut row_problems: Vec<Arc<Problem>> = problems.to_vec();
let mut assignments = random_assignments(problems, &mut rng);
let mut solutions: Vec<Option<Solution>> = vec![None; problems.len()];
let preprocessing_start = Instant::now();
let mut state = self.architecture.setup(problems)?;
let preprocessing_runtime = preprocessing_start.elapsed().as_secs_f64();
while !stop.is_exhausted() && solutions.iter().any(Option::is_none) {
let pending: Vec<bool> = active
.iter()
.map(|&problem_idx| solutions[problem_idx].is_none())
.collect();
state.step(&row_problems, &mut assignments, &pending, &mut rng);
stop.tick();
let solved_now: Vec<bool> = crate::utils::worker_pool().install(|| {
assignments
.par_iter()
.zip(row_problems.par_iter())
.zip(pending.par_iter())
.map(|((row, problem), &is_pending)| is_pending && problem.is_solution(row))
.collect()
});
state.solved(&solved_now);
for (row, &problem_idx) in active.iter().enumerate() {
if solved_now[row] {
solutions[problem_idx] = Some(
Solution::satisfiable(&problems[problem_idx], assignments[row].clone())
.with_runtime(stop.start.elapsed().as_secs_f64(), preprocessing_runtime)
.with_iterations(stop.iters_done),
);
if let Some(bar) = progress {
bar.inc(1);
}
}
}
if let Some(bar) = progress {
bar.set_message(format!("Solving instances (iteration {})", stop.iters_done));
}
if stop.iters_done.is_multiple_of(Self::COMPACTION_INTERVAL) {
let keep: Vec<bool> = active
.iter()
.map(|&problem_idx| solutions[problem_idx].is_none())
.collect();
if keep.iter().any(|&kept| !kept) {
state.retain(&keep);
row_problems = filtered(row_problems, &keep);
assignments = filtered(assignments, &keep);
active = filtered(active, &keep);
}
}
}
Ok(solutions
.into_iter()
.map(|s| {
s.unwrap_or_else(|| {
Solution::unknown()
.with_runtime(stop.start.elapsed().as_secs_f64(), preprocessing_runtime)
.with_iterations(stop.iters_done)
})
})
.collect())
}
}
pub fn run_batched(
engine: &LocalSearch,
problems: &[Arc<Problem>],
batch_size: Option<usize>,
budget: Budget,
seed: u64,
) -> Result<Vec<Solution>, String> {
let batch_size = batch_size.unwrap_or(problems.len()).max(1);
let batches: Vec<&[Arc<Problem>]> = problems.chunks(batch_size).collect();
log::info!(
"Solving {} problems in {} batches of at most {}",
problems.len(),
batches.len(),
batch_size,
);
let progress = ProgressBar::new(problems.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("Solving instances");
let mut solutions = Vec::with_capacity(problems.len());
for (batch_idx, batch) in batches.iter().enumerate() {
let batch_start = Instant::now();
let batch_solutions = engine.run(
batch,
budget,
seed.wrapping_add(batch_idx as u64),
Some(&progress),
)?;
log_status_counts(
&format!(
"batch {}/{} done in {:.1}s",
batch_idx + 1,
batches.len(),
batch_start.elapsed().as_secs_f64()
),
&batch_solutions,
);
let unsolved = batch_solutions
.iter()
.filter(|s| matches!(s.status(), Status::Unknown))
.count();
progress.inc(unsolved as u64);
solutions.extend(batch_solutions);
}
progress.finish_and_clear();
log_status_counts("Done", &solutions);
Ok(solutions)
}
fn log_status_counts(label: &str, solutions: &[Solution]) {
let count = |wanted: Status| solutions.iter().filter(|s| s.status() == wanted).count();
let (sat, unsat) = (count(Status::Satisfiable), count(Status::Unsatisfiable));
log::info!(
"{label}: {sat} sat, {unsat} unsat, {} unknown/timed out (of {})",
solutions.len() - sat - unsat,
solutions.len(),
);
}
pub fn solve(
problems: &[Arc<Problem>],
config: &SolveConfig,
checkpoint_dir: Option<&Path>,
) -> Result<Vec<Solution>, String> {
if problems.is_empty() {
return Err("local search: there are no problems to solve".to_string());
}
let seed = config
.seed
.unwrap_or_else(|| crate::utils::with_rng(|rng| rng.random_range(0..u64::MAX)));
match &config.search {
SearchConfig::BeliefPropagation(search) => {
if checkpoint_dir.is_some() {
return Err(
"the belief-propagation search uses no network: do not give a checkpoint"
.to_string(),
);
}
let engine = LocalSearch::new(Box::new(BeliefPropagationSearch::new(search)));
run_batched(&engine, problems, config.batch_size, config.budget, seed)
}
#[cfg(feature = "learning")]
_ => neural_prior::solve_with_consformer(problems, config, checkpoint_dir, seed),
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::destroy::DestroyOperator;
use std::time::Duration;
struct CallCounter {
calls: std::sync::Mutex<std::collections::HashMap<usize, usize>>,
}
impl DestroyOperator for CallCounter {
fn destroy(
&self,
problem: &Problem,
_assignment: &[isize],
_rng: &mut StdRng,
) -> Vec<usize> {
*self
.calls
.lock()
.unwrap()
.entry(problem as *const Problem as usize)
.or_default() += 1;
Vec::new()
}
}
struct Idle(Arc<CallCounter>);
impl SearchArchitecture for Idle {
fn setup<'a>(
&'a self,
_problems: &[Arc<Problem>],
) -> Result<Box<dyn SearchState + 'a>, String> {
Ok(Box::new(IdleState { counter: &self.0 }))
}
}
struct IdleState<'a> {
counter: &'a CallCounter,
}
impl SearchState for IdleState<'_> {
fn step(
&mut self,
problems: &[Arc<Problem>],
assignments: &mut [Vec<isize>],
pending: &[bool],
rng: &mut StdRng,
) {
destroy_rows(self.counter, problems, assignments, pending, rng);
}
}
fn three_binary_variables(unsatisfiable: bool) -> Arc<Problem> {
let mut problem = Problem::default();
let vars: Vec<_> = (0..3).map(|_| problem.add_variable(vec![0, 1])).collect();
if unsatisfiable {
crate::constraints::all_different(&mut problem, vars);
}
Arc::new(problem)
}
#[test]
fn unsolved_problems_keep_being_destroyed_after_others_were_compacted_away() {
let problems = vec![
three_binary_variables(false),
three_binary_variables(false),
three_binary_variables(true),
three_binary_variables(true),
];
let counter = Arc::new(CallCounter {
calls: Default::default(),
});
let search = LocalSearch::new(Box::new(Idle(counter.clone())));
let budget = Budget {
time_limit: Duration::MAX,
iteration_limit: 250,
};
let solutions = search.run(&problems, budget, 0, None).unwrap();
assert!(solutions[0].assignment().is_some() && solutions[1].assignment().is_some());
assert!(solutions[2].assignment().is_none() && solutions[3].assignment().is_none());
let calls = counter.calls.lock().unwrap();
for unsolved in &problems[2..] {
let key = Arc::as_ptr(unsolved) as usize;
assert_eq!(calls[&key], 250);
}
}
#[test]
fn the_seed_of_a_run_decides_where_it_starts_and_how_it_goes() {
use crate::constraints::all_different;
let mut problem = Problem::default();
let vars = problem.add_variables(8, (0..8).collect());
all_different(&mut problem, vars);
let problems = vec![Arc::new(problem)];
let search = LocalSearch::new(Box::new(BeliefPropagationSearch::new(
&BeliefPropagationSearchConfig {
destroy_fraction: 0.3,
..BeliefPropagationSearchConfig::default()
},
)));
let budget = Budget {
time_limit: Duration::MAX,
iteration_limit: 500,
};
let first = search.run(&problems, budget, 7, None).unwrap();
let second = search.run(&problems, budget, 7, None).unwrap();
assert_eq!(first[0].iterations(), second[0].iterations());
assert_eq!(first[0].assignment(), second[0].assignment());
}
}