Contents Menu Expand Light mode Dark mode Auto light/dark, in light mode Auto light/dark, in dark mode Skip to content
Aicad 1.0.0-rc.1
Light Logo Dark Logo
Aicad 1.0.0-rc.1

Getting started

  • Installation

Python guide

  • Modelling
  • Compiling a model
  • Relaxed diagrams and refinement
  • Local search
  • Training a network

Rust guide

  • Modelling
  • Compiling a problem
  • Relaxed diagrams and refinement
  • Local search
  • Training a network

Reference

  • Python API reference
  • All-items Rust API
  • Benchmarks

Contributing

  • Contributing
    • Orientation
    • Adding a constraint
    • Adding a destroy operator
    • Adding a local-search architecture
    • Adding a neural network
    • Before you open a pull request
Back to top
View this page

Local search¶

A compiled diagram answers questions about a problem; a local search finds solutions to problems that are too large to compile. Every search runs the same loop. It starts from a random assignment, and at each iteration destroys some variables (frees them) and repairs them (picks new values that satisfy the constraints as well as it can), until it finds a solution or reaches a limit. The searches differ only in how they repair:

  • the belief propagation search repairs with belief propagation on the diagrams of the constraints, from uniform probabilities. It needs nothing but the problems;

  • the neural prior searches (NeuralPrior, NeuralPriorBp) start from the predictions of a trained network (see Training a network; needs the learning feature).

A local search finds solutions but cannot prove that there are none: to prove it, compile the problem. Many problems can be searched together: they are stepped as one batch. A search that is not one of these, or a different destroy operator, can be plugged in from your own crate: see Contributing.

A problem family¶

The examples use random graph colourings: a graph with 30 nodes and 3 colours, drawn so that a colouring is known to exist. Generating problems is up to you; the library only sees the problems.

use std::sync::Arc;

use aicad::constraints::not_equals;
use aicad::modelling::Problem;
use rand::rngs::StdRng;
use rand::{RngExt, SeedableRng};

/// A random feasible graph colouring: hide a colouring, then draw edges between nodes of other
/// colours only, so that the hidden colouring is a solution. `degree` is the average number of
/// neighbours of a node.
pub fn coloring(rng: &mut StdRng, nodes: usize, colours: usize, degree: f64) -> Arc<Problem> {
    let hidden: Vec<usize> = (0..nodes).map(|_| rng.random_range(0..colours)).collect();
    let mut problem = Problem::default();
    let colour = problem.add_variables(nodes, (0..colours as isize).collect());
    let pairs: Vec<(usize, usize)> = (0..nodes)
        .flat_map(|i| (i + 1..nodes).map(move |j| (i, j)))
        .filter(|&(i, j)| hidden[i] != hidden[j])
        .collect();
    let probability = (degree * nodes as f64 / 2.0 / pairs.len() as f64).min(1.0);
    for (i, j) in pairs {
        if rng.random::<f64>() < probability {
            not_equals(&mut problem, colour[i], colour[j]);
        }
    }
    Arc::new(problem)
}

Running a search¶

solve takes the problems (all of them are stepped together as one batch unless batch_size says otherwise), a SolveConfig and, for the neural searches, a checkpoint. The configuration holds the limits, which apply to each batch (whichever is reached first stops the search), the seed that makes the run reproducible, and the architecture of the search with its settings.

The default search destroys every variable at each iteration, which is a restart from scratch. Destroying only a fraction makes it a real local search; destroy_kind chooses which ones: at random, where the constraints are violated (Worst), or around a variable (Related).

    use aicad::destroy::DestroyKind;
    use aicad::local_search::{BeliefPropagationSearchConfig, SearchConfig, SolveConfig, solve};
    use aicad::modelling::Status;

    let mut rng = StdRng::seed_from_u64(0);
    let problems: Vec<_> = (0..20).map(|_| coloring(&mut rng, 30, 3, 4.0)).collect();

    // The limits apply to each batch; whichever is reached first stops the search. The default
    // architecture is belief propagation, and the default destroys everything at each iteration,
    // which is a restart from scratch.
    let limits = SolveConfig::default()
        .with_runtime_limit(5)
        .with_iteration_limit(300)
        .with_seed(0);
    let solutions = solve(&problems, &limits, None).unwrap();
    let solved = solutions
        .iter()
        .filter(|s| s.status() == Status::Satisfiable)
        .count();
    println!("destroy everything: solved {solved} of {}", problems.len());

    // Destroying only a fraction of the variables makes it a real local search; `destroy_kind`
    // chooses which ones: at random, where the constraints are violated, or around a variable.
    for destroy_kind in [
        DestroyKind::Random,
        DestroyKind::Worst,
        DestroyKind::Related,
    ] {
        let search = BeliefPropagationSearchConfig {
            destroy_kind,
            destroy_fraction: 0.2,
            ..BeliefPropagationSearchConfig::default()
        };
        let config = limits
            .clone()
            .with_search(SearchConfig::BeliefPropagation(search));
        let solutions = solve(&problems, &config, None).unwrap();
        let solved = solutions
            .iter()
            .filter(|s| s.status() == Status::Satisfiable)
            .count();
        println!(
            "destroy {destroy_kind:?} 20%: solved {solved} of {}",
            problems.len()
        );
    }

Results¶

A Solution carries the assignment when one was found, its status, and how the search went. The same seed gives the same run: the seed decides where the search starts and every choice it makes.

    let search = BeliefPropagationSearchConfig {
        destroy_kind: DestroyKind::Worst,
        destroy_fraction: 0.2,
        ..BeliefPropagationSearchConfig::default()
    };
    let config = SolveConfig::default()
        .with_runtime_limit(5)
        .with_iteration_limit(300)
        .with_seed(0)
        .with_search(SearchConfig::BeliefPropagation(search));
    let solutions = solve(&problems[..1], &config, None).unwrap();
    let solution = &solutions[0];
    println!(
        "{:?} after {:?} iterations",
        solution.status(),
        solution.iterations()
    );
    if let Some(assignment) = solution.assignment() {
        assert!(problems[0].is_solution(assignment));
    }

    // The same seed gives the same run.
    let again = solve(&problems[..1], &config, None).unwrap();
    println!(
        "reproducible: {}",
        again[0].iterations() == solution.iterations()
    );

aicad::set_num_threads fixes how many threads the library uses for its own work.

Next
Training a network
Previous
Relaxed diagrams and refinement
Copyright ©
Made with Sphinx and @pradyunsg's Furo
On this page
  • Local search
    • A problem family
    • Running a search
    • Results