Skip to content
FZnSO

Implementing a solver

Implementing a solver means exporting thirteen entry points from a dynamically loadable library. You do not have to write them by hand: the Rust and C++ bindings each provide a macro that writes all thirteen and leaves you the three or four methods that actually differ between solvers.

What you must decide first

Section titled “What you must decide first”

Your solver’s name. It goes in every symbol (fznso_gecode_solver_run) and must match the library’s file name, so a loader can recover it. It must be a valid C identifier not starting with lib; see Naming & versioning.

What you will declare. Five capability lists say what your solver accepts. Start with all of them empty and add as you go; declaring nothing is conforming. Where a name appears in the registry, declaring it commits you to the registry’s meaning.

The three methods that matter

Section titled “The three methods that matter”

Everything else is bookkeeping the macros handle.

  • option_set and option_get — accept the options you declared, reject the rest with a message.
  • run — read the model, search, report each solution, return a status.
  • statistic — report the solver-scoped statistics you declared, absent for anything else.

Reading the model

Section titled “Reading the model”

The model is a callback table, not a structure. Ask it what it holds:

for i in 0..model.decision_count() {
    let ty = model.decision_type(i);
    let domain = model.decision_domain(i);   // may be absent — no explicit domain
}
for c in 0..model.constraint_count() {
    let ident = model.constraint_ident(c);   // e.g. "int_lin_le"
    for a in 0..model.constraint_argument_count(c) {
        let arg = model.constraint_argument(c, a);
    }
}

Two rules govern everything you read, and both are stated in full: ask a value its kind before reading it, and treat what you read as borrowed for the duration of run.

Reporting

Section titled “Reporting”

Call the solution callback once per solution. The values you hand it are borrowed from you, so the storage behind them must outlive the call. Build it before reporting, not inside the accessor.

Two callbacks are nullable, and the difference is worth honouring: a null on_message means skip building the diagnostic, not build it and discard it — both bindings expose this as a wanted() check — and a null should_stop means drop the poll from your search loop rather than call a predicate that always answers false.

Failing

Section titled “Failing”

Return FznsoError from run, or a message from option_set. The caller then asks for the reason through fznso_<name>_solver_read_error. Do not report failures through on_message; that channel is for diagnostics the search survived.

A complete example

Section titled “A complete example”

This solver is deliberately trivial (it assigns every decision the lower bound of its domain and ignores the constraints) so that the shape is what shows through. It is built and run by the test suite on every commit, so it cannot drift from the interface.

rust/fznso/examples/example_solver.rs
//! A throwaway FZnSO solver, built as a `cdylib` example so the dynamic-loading
//! path can be tested end to end.
//!
//! This is **not** a real solver: it assigns every decision variable the lower
//! bound of its domain and reports that as a solution, ignoring the constraints
//! entirely. It exists so `tests/dylib.rs` (and the C++ and Python suites) have
//! something to `dlopen`, exercising [`fznso::Library`], [`fznso::DynSolver`]
//! and the entry points generated by [`fznso::fznso_export`].
//!
//! Being an example rather than its own crate, it is the canonical Rust solver
//! implementation the whole workspace loads. Replace it once a real solver
//! exists to test against.


#![allow(missing_docs, reason = "the exported ABI entry points are generated")]


use std::marker::PhantomData;


use fznso::{
  Model, Solution, Solver, SolverType, Statistic, StatisticList, Status, Str, Type, TypeBase,
  Value, ValueExt, ValueView,
};


/// The assignment produced by [`ExampleSolver`].
#[derive(Debug)]
pub struct ExampleSolution {
  /// The value assigned to each decision variable, indexed by decision index.
  values: Vec<i64>,
  /// How many solutions had been emitted when this one was produced.
  index: i64,
}


impl Solution for ExampleSolution {
  fn statistic(&self, name: &str) -> Value<'_> {
    match name {
      "solutions" => (&self.index).into(),
      _ => (&()).into(),
    }
  }


  fn value(&self, decision_idx: usize) -> Value<'_> {
    self.values
      .get(decision_idx)
      .map_or_else(|| (&()).into(), Into::into)
  }
}


/// A solver that reports domain lower bounds, ignoring all constraints.
#[derive(Debug, Default)]
pub struct ExampleSolver {
  /// Value of the `solution_limit` option: how many solutions to emit.
  solution_limit: i64,
  /// How many times [`Solver::run`] has been called, reported as the
  /// solver-level `runs` statistic.
  runs: i64,
}


/// An integer statistic, the only shape this fixture reports.
const INT_STAT: Type = Type {
  list_of: false,
  decision: false,
  set_of: false,
  opt: false,
  base: TypeBase::FznsoTypeBaseInt,
};


/// The statistics this fixture reports, one of each scope: `solutions` is read
/// from a solution, `runs` from the solver instance. A statistic may also set
/// both flags, in which case either route works.
const STATS: &[Statistic<'static>] = &[
  Statistic {
    ident: Str::new("solutions"),
    ty: INT_STAT,
    solution: true,
    solver: false,
    lifetime: PhantomData,
  },
  Statistic {
    ident: Str::new("runs"),
    ty: INT_STAT,
    solution: false,
    solver: true,
    lifetime: PhantomData,
  },
];


impl Solver for ExampleSolver {
  type Solution<'s> = ExampleSolution;


  fn option_get(&self, name: &str) -> Value<'_> {
    match name {
      "solution_limit" => (&self.solution_limit).into(),
      _ => (&()).into(),
    }
  }


  fn statistic(&self, name: &str) -> Value<'_> {
    match name {
      "runs" => (&self.runs).into(),
      _ => (&()).into(),
    }
  }


  fn option_set(&mut self, name: &str, value: Value<'_>) -> Result<(), String> {
    match name {
      "solution_limit" => {
        self.solution_limit = i64::try_from(&value)
          .map_err(|()| "solution_limit expects an integer".to_owned())?;
        Ok(())
      }
      _ => Err(format!("unknown option `{name}`")),
    }
  }


  fn run<M, F, G, H>(
    &mut self,
    model: &M,
    on_solution: &mut F,
    on_message: Option<&mut G>,
    should_stop: Option<&H>,
  ) -> Status
  where
    M: Model + Sync,
    F: for<'s> FnMut(&'s Self::Solution<'s>) + Send,
    G: FnMut(&str, Value<'_>) + Send,
    H: Fn() -> bool + Send + Sync,
  {
    self.runs += 1;


    // This fixture ignores the constraints, which is worth saying out loud —
    // but only builds the message if someone is listening for it.
    let mut on_message = on_message;
    if let Some(emit) = &mut on_message {
      let warning = format!("ignoring {} constraint(s)", model.constraint_len());
      emit("warn", (&warning).into());
    }


    // Report the per-layer decision counts when the model has more than one
    // layer, so tests can observe that the layer structure came through.
    if model.layer_len() > 1 && on_message.is_some() {
      let counts: Vec<String> = model
        .layers()
        .map(|layer| layer.decisions().count().to_string())
        .collect();
      if let Some(emit) = &mut on_message {
        emit("layers", (&counts.join(",")).into());
      }


      // Also read back the model's strings and a constraint argument, so
      // tests can observe those cross the interface too.
      let name0 = model
        .decision(fznso::DecisionIdx::from(0))
        .name()
        .unwrap_or("");
      let mut summary = format!("obj={};name0={}", model.objective().ident(), name0);
      if model.constraint_len() > 0 {
        let con = model.constraint(fznso::ConstraintIdx::from(0));
        summary += &format!(";con0={}({})", con.ident(), con.argument(0).get_int());
      }
      if let Some(emit) = &mut on_message {
        emit("model", (&summary).into());
      }
    }


    // Lower bound of each decision's domain, or 0 when it has none.
    let base: Vec<i64> = model
      .decisions()
      .map(|d| match d.domain().view() {
        ValueView::IntSet(set) if !set.is_empty() => set.get(0).0,
        _ => 0,
      })
      .collect();


    // Absent means "never asks to stop", so there is nothing to poll.
    let stopped = || should_stop.is_some_and(|poll| poll());
    // Polled before starting, and again after each solution is reported, so a
    // caller can stop from inside its own callback.
    if stopped() {
      return Status::Incomplete;
    }
    for i in 0..self.solution_limit {
      // Shift the first variable each round so successive solutions differ.
      let mut values = base.clone();
      if let Some(first) = values.first_mut() {
        *first += i;
      }
      on_solution(&ExampleSolution { values, index: i });
      if stopped() {
        return Status::Incomplete;
      }
    }
    Status::Complete
  }
}


impl SolverType for ExampleSolver {
  /// The statistic list is declared so the `solution`/`solver` scope flags
  /// are exercised; the other capability lists keep their empty default.
  const STATISTIC_LIST: StatisticList<'static> = StatisticList {
    len: STATS.len(),
    stats: STATS.as_ptr(),
    lifetime: PhantomData,
  };


  fn new() -> Self {
    Self {
      solution_limit: 1,
      runs: 0,
    }
  }
}


// The library name matches the built cdylib's base name
// (`libexample_solver.*`), so `Library::new` recovers it from the file name.
fznso::fznso_export!(ExampleSolver, "example_solver");

Searching on several threads

Section titled “Searching on several threads”

If you search in parallel, the threading contract applies: the model is yours to read from any number of threads, but the solution and message callbacks must be driven serially, so funnel them through one thread. This example does exactly that.

rust/fznso/examples/threaded_solver.rs
//! A solver that does all of its work on a worker thread, so the threading
//! contract in [`fznso::Solver::run`] is exercised end to end.
//!
//! It is deliberately trivial *as a solver*: it assigns every decision the same
//! value and reports one solution. What matters is **where** the work happens.
//! The model is read, and both callbacks are invoked, from a spawned thread —
//! which is exactly what the contract permits and what a real parallel solver
//! does. That makes this the fixture for two properties nothing else covers:
//!
//! - the `M: Sync` / `F: Send` / `G: Send` bounds, and the `unsafe impl Sync`
//!   on `ModelRefAdapter`, are actually relied upon rather than merely
//!   declared;
//! - a binding that holds a process-wide lock across the run — the Python GIL,
//!   say — deadlocks against this, so loading it proves the lock is released.
//!
//! The contract still requires reporting to be *serial*, which it is here:
//! only one thread ever calls the callbacks, and the main thread just waits.


#![allow(missing_docs, reason = "the exported ABI entry points are generated")]


use fznso::{Model, Solution, Solver, SolverType, Status, Value};


/// The solution reported from the worker thread.
#[derive(Debug)]
pub struct ThreadedSolution {
  /// How many decisions the worker read from the model, reported as every
  /// decision's value so a consumer can observe that the cross-thread read
  /// reached the real model.
  decisions: i64,
}


impl Solution for ThreadedSolution {
  fn statistic(&self, name: &str) -> Value<'_> {
    match name {
      "decisions" => (&self.decisions).into(),
      _ => (&()).into(),
    }
  }


  fn value(&self, _decision_idx: usize) -> Value<'_> {
    (&self.decisions).into()
  }
}


/// A solver that reports from a thread other than the one `run` was called on.
#[derive(Debug, Default)]
pub struct ThreadedSolver;


impl Solver for ThreadedSolver {
  type Solution<'s> = ThreadedSolution;


  fn option_get(&self, _name: &str) -> Value<'_> {
    (&()).into()
  }


  fn option_set(&mut self, name: &str, _value: Value<'_>) -> Result<(), String> {
    Err(format!("unknown option `{name}`"))
  }


  fn run<M, F, G, H>(
    &mut self,
    model: &M,
    on_solution: &mut F,
    on_message: Option<&mut G>,
    should_stop: Option<&H>,
  ) -> Status
  where
    M: Model + Sync,
    F: for<'s> FnMut(&'s Self::Solution<'s>) + Send,
    G: FnMut(&str, Value<'_>) + Send,
    H: Fn() -> bool + Send + Sync,
  {
    // A scoped thread, so the borrowed model and callbacks need no `'static`.
    // Reading the model here is what requires `M: Sync`; reporting from here
    // is what requires the callbacks to be `Send`.
    std::thread::scope(|scope| {
      let mut on_message = on_message;
      let stopped = || should_stop.is_some_and(|poll| poll());
      let worker = scope.spawn(move || {
        if stopped() {
          return Status::Incomplete;
        }
        let decisions = i64::try_from(model.decision_len()).unwrap_or(-1);
        // Only formatted when someone is listening.
        if let Some(emit) = &mut on_message {
          let note = format!("read {decisions} decision(s) from a worker thread");
          emit("log", (&note).into());
        }
        on_solution(&ThreadedSolution { decisions });
        if stopped() {
          return Status::Incomplete;
        }
        Status::Complete
      });
      worker
        .join()
        .unwrap_or_else(|_| Status::Error("the worker thread panicked".to_owned()))
    })
  }
}


impl SolverType for ThreadedSolver {
  /// This fixture declares no capabilities; only the constructor is required.
  fn new() -> Self {
    Self
  }
}


// The library name matches the built cdylib's base name
// (`libthreaded_solver.*`), so `Library::new` recovers it from the file name.
fznso::fznso_export!(ThreadedSolver, "threaded_solver");

Checking your work

Section titled “Checking your work”

Point the test consumers at your library. They exercise the whole interface: options, statistics, solutions, messages, early stopping, and a model published back across the interface and compared against the original:

Terminal window
just test-cpp                                  # builds and runs test_consumer
./target/test_consumer /path/to/libmysolver.so

If you are writing the solver in Rust, run the suite under miri as well. Every bug in the handle-casting class this interface can produce passed the ordinary test suite first:

Terminal window
just miri