Adding a local-search architecture¶
A local search repeatedly destroys part of each assignment and repairs it, until every problem is
solved or the budget is spent. The engine (LocalSearch) runs that loop and keeps the budget and
the list of solved problems. What a step does belongs to the architecture, which implements
two small traits in src/local_search/mod.rs:
SearchArchitecture::setup(problems)builds the state of a search over a batch of problems, or returns an error naming the restriction when the architecture cannot search them together.SearchState::step(problems, assignments, pending, rng)performs one iteration: it destroys and repairs the assignments of the rows flagged inpendingand leaves the others as they are.solvedandretainlet it free per-row data; both do nothing by default.
The engine owns the assignments; the state holds only what the architecture needs besides them.
From another crate¶
Implement the two traits, wrap the architecture in LocalSearch::new(Box::new(...)) and run it with
run_batched, which batches the problems, applies the budget and seeds each batch. The helpers
destroy_rows and row_seeds are public, so that a step can reuse the destroy operators and keep
its randomness reproducible. tests/custom_search.rs is a complete, compiled example: an
architecture that redraws the destroyed variables at random.
Into this crate, and into Python¶
Write the architecture in
src/local_search/<name>.rs, with a settings struct next to it (Defaultincluded). The existingbp_search.rsis the model for a search that needs no network;neural_prior.rsfor one that does.Add a variant holding the settings to
SearchConfiginsrc/local_search/config.rs(gated onlearningif it needs burn), and handle it insolveinsrc/local_search/mod.rs.Add a variant to
PySearchinsrc/pyaicad/local_search.rswith its conversion. A pyo3 enum cannot gate variants on a feature, so a variant that needslearningstays and the conversion returns an error without it.Add the search class to
python/pyaicad/search.py(frozen dataclass, defaults,with_, validation in__post_init__,require_learningif it needs the full build), export it, and add it to_core.pyianddocs/api.md.
Worked example: a random repair¶
tests/custom_search.rs is compiled as a separate crate, so everything in it is public API. The
architecture destroys some variables with any DestroyOperator and repairs them by redrawing their
values at random: the simplest repair there is.
/// Destroys some variables and gives them a random value.
struct Redraw {
destroy: Box<dyn DestroyOperator>,
}
struct RedrawState<'a> {
architecture: &'a Redraw,
}
impl SearchArchitecture for Redraw {
fn setup<'a>(&'a self, problems: &[Arc<Problem>]) -> Result<Box<dyn SearchState + 'a>, String> {
if problems.iter().any(|p| p.number_variables() == 0) {
return Err("a problem without variables cannot be searched".to_string());
}
Ok(Box::new(RedrawState { architecture: self }))
}
}
impl SearchState for RedrawState<'_> {
fn step(
&mut self,
problems: &[Arc<Problem>],
assignments: &mut [Vec<isize>],
pending: &[bool],
rng: &mut StdRng,
) {
let destroyed = destroy_rows(
self.architecture.destroy.as_ref(),
problems,
assignments,
pending,
rng,
);
for ((row, problem), freed) in assignments.iter_mut().zip(problems).zip(destroyed) {
let fresh = random_assignment(problem);
for variable in freed {
row[variable] = fresh[variable];
}
}
}
}
Reading it from the top:
Redrawis the architecture. It holds what is common to all problems (here the destroy operator) and is shared between runs.setupis called once per batch, and builds the state. It is the place to refuse what the architecture cannot search, with an error that says why; the engine passes that error to the caller ofrun_batched.stepdoes one iteration for all the rows at once.destroy_rowsasks the operator for the variables of each pending row, in parallel and reproducibly (it draws one seed per row fromrng), then the repair writes the new values straight intoassignments.Rows not in
pendingare already solved: leave them as they are.
Running it takes the engine, the problems, a batch size, a budget and a seed:
#[test]
fn a_search_from_another_crate_runs_in_the_engine() {
let engine = LocalSearch::new(Box::new(Redraw {
destroy: DestroyKind::Random.build(0.5),
}));
let problems = vec![chain(3), chain(3)];
let budget = Budget {
iteration_limit: 5_000,
..Budget::default()
};
let solutions = run_batched(&engine, &problems, None, budget, 0).unwrap();
assert_eq!(solutions.len(), 2);
for solution in &solutions {
assert_eq!(solution.status(), Status::Satisfiable);
}
}
A real repair replaces the loop in step. bp_search.rs repairs with belief propagation on the
diagrams of the constraints, and neural_prior.rs with the logits of a network; both keep per-row
data in their state, which is what solved and retain are for.
Tests¶
It solves small satisfiable problems, and leaves already-satisfying assignments alone.
Two runs with the same seed give the same iterations.
setuprefuses what the architecture cannot search, with a message that names the restriction.A batch with several problems gives each the same result as running it alone.