Design

This guide covers the library internals for contributors.

See Numeric types and arithmetic before choosing numeric fields or implementing arithmetic in a model or reduction.

Module Architecture

Problem Model

Every problem implements Problem. The associated Value type is the per-configuration aggregate returned by evaluate(). Solvers fold these values across the configuration space, and witness-capable aggregates can also recover representative configurations.

trait Problem: Clone {
    const NAME: &'static str;              // e.g., "MaximumIndependentSet"
    type Solution;                         // e.g., Vec<bool>, permutation, tuple
    type Value: Clone;                     // e.g., Max<i64>, Or, Sum<i64>
    fn parameter_names() -> &'static [&'static str];
    fn parameters(&self) -> ProblemParameters;
    fn evaluate(&self, solution: &Self::Solution) -> Result<Self::Value, EvaluationError>;
    fn variant() -> Vec<(&'static str, &'static str)>; // e.g., [("graph", "SimpleGraph"), ("weight", "i64")]
    fn problem_type() -> ProblemType;      // default: registry lookup by NAME
}

• Problem — the base trait. Every problem declares a mathematical Solution type, evaluates that type directly, and reports its canonical instance parameters. For example, a 4-vertex MIS uses Vec<bool>; evaluate(&[true, false, true, false]) returns Ok(Max(Some(2))) if vertices 0 and 2 form an independent set, or Ok(Max(None)) if they share an edge. Inherent getters such as num_vertices() and num_edges() supply the named parameters used by reduction expressions.
• BruteForceProblem — the reference-solver capability for registered variants with a finite Cartesian coordinate space. Its dimensions() method and the Cartesian iterator belong to the brute-force solver, not to the mathematical Problem contract.
• Objective problems — typically use Max<V>, Min<V>, or Extremum<V> as Value.
• Feasibility problems — typically use Or.
• Solve contract — a successful solve always returns the problem’s Solution; a global count or statistic without a representative solution is not a Problem solve.
• Common aggregate wrappers — Max<V>, Min<V>, Sum<W>, Or, And, Extremum<V>, ExtremumSense.

Construction inputs

VariantEntry::inputs() describes the values a concrete constructor accepts. Models with a separate construction specification supply CreateSpec::inputs(); direct constructors use their declared fields. CLI creation, MCP creation, and pred show use this contract. Model-level catalog fields describe the model family; they are not a concrete variant’s input schema. show exposes concrete inputs in JSON and labels them Inputs in text.

Unit-valued data are implicit in One variants. For example, MVC/One accepts a graph, while MVC/i64 also accepts vertex weights. Constructors derive unit-vector lengths from the graph, set family, or task deadlines. Internal Vec<One> storage and persisted instance JSON remain independent of construction inputs. Supplying an undeclared weight or length input is an error, even when every value is one.

Decision<P> composes the registered inputs of P with an objective bound and calls P’s registered constructor before wrapping the result. It does not repeat the inner input schema or deserialize construction inputs as persisted model JSON.

Numeric types and arithmetic

Numeric formats are selected by semantic role:

• usize represents in-memory indices, collection lengths, and brute-force dimensions;
• u64 represents public problem parameters and the input/output values of reduction parameter expressions;
• i64 represents signed mathematical integers;
• bool represents Boolean variables; and
• finite f64 represents real or rational values when an approximate representation is part of the model contract.

usize is not a portable serialized parameter format, and u64 is not an index or general-purpose replacement for a model’s mathematical integer domain.

Another numeric format requires sufficient justification from the mathematical problem or target schema. Required exceptions include BigUint in Factoring, SubsetSum, SubsetProduct, QuadraticCongruences, and QuadraticDiophantineEquations, where arbitrary precision is part of the problem, and One in unweighted variants, where the type represents the unit-weight domain. Implementation convenience is not sufficient justification. There is no i32 model or I/O numeric format.

This contract applies only at model, result, reduction-target, and external I/O boundaries; implementation-local values are outside its scope. For example, SpinGlass couplings and its objective result use i64, while the temporary {−1, +1} spin values used inside evaluate() need not. A reduction’s temporary calculations are also outside the contract, but numeric fields written into its target model must follow the target model’s numeric format.

Weight variants are One, i64, and f64, with One ⊂ i64 ⊂ f64. i64 → f64 is a fallible reduction using a checked conversion in ±(2^53-1), not as f64.

Arithmetic

• Keep arithmetic in the declared type. Exact values use checked i64 operations; approximate values use finite f64 operations.
• Constructors and reductions reject an arithmetic step that would overflow i64 when producing a stored field. They do not cap every magnitude at 2^53-1. evaluate() never widens, wraps, saturates, or silently approximates.
• Do not promote an i64 calculation to i128, BigInt, or BigUint to accept a larger instance.

Boundaries

• Use From only for value-preserving conversions and TryFrom when range, sign, or domain can change. Do not use as for model-derived values.
• Converting a registered parameter getter from usize to u64 is an internal invariant of Problem::parameters(), not a recoverable construction error. A valid instance’s registered parameters must already fit u64; the implementation checks this conversion to prevent silent truncation.
• Symbolic parameter evaluation may use arbitrary-precision integers for local intermediate arithmetic, but a materialized ProblemParameters must fit u64.
• An i64 to f64 conversion is explicit and fallible: it succeeds only for |value| ≤ 2^53-1. Use one shared helper at weight casts, solver adapters, and other exact-to-float hubs.
• A lattice-to-UnitDiskGraph reduction converts coordinates fallibly and rejects a stored f64 geometry that would change source adjacency.
• Rust constructors keep i64 fields as i64. CLI and MCP JSON encoding of an i64 with |value| > 2^53-1 errors; there is no string encoding and no clamping.

Variant System

A single problem name like MaximumIndependentSet can have multiple variants. Each variant is identified by dimension-value pairs such as {graph: "SimpleGraph", weight: "i64"}. Concrete variants are registered nodes in the reduction graph, and explicit reduction rules connect them.

Variant types fall into three categories:

• Graph type — SimpleGraph, PlanarGraph, BipartiteGraph, UnitDiskGraph, KingsSubgraph, TriangularSubgraph.
• Weight type — One (unweighted), i64, f64.
• K value — e.g., K3 for 3-SAT, KN for arbitrary K.

pub trait VariantParam: 'static {
    const CATEGORY: &'static str;     // e.g., "graph", "weight", "k"
    const VALUE: &'static str;        // e.g., "SimpleGraph", "i64"
}

impl_variant_param!(SimpleGraph, "graph");

impl_variant_param!(KN, "k", k: None);

impl_variant_param!(K3, "k", k: Some(3));

impl_variant_reduction!(
    MaximumIndependentSet,
    <UnitDiskGraph, i64> => <SimpleGraph, i64>,
    fields: [num_vertices, num_edges],
    |src| MaximumIndependentSet::new(
        SimpleGraph::new(
            src.num_vertices(),
            Graph::edges(src.graph()),
        ),
        src.weights().to_vec())
);

// MaximumIndependentSet<G: VariantParam, W: VariantParam>
fn variant() -> Vec<(&'static str, &'static str)> {
    crate::variant_params![G, W]
    // e.g., MaximumIndependentSet<UnitDiskGraph, One>
    //     -> vec![("graph", "UnitDiskGraph"), ("weight", "One")]
}

Reduction Rules

Mathematical contract

A single-instance reduction from A to B constructs a legal target instance F(x) and recovers a correct source answer G(x, y) from any correct target answer y. F and G run in polynomial time in their encoded inputs.

“Correct answer” means YES/NO, a valid witness, an optimal solution, or a total count, according to the problem; infeasibility must be represented explicitly or excluded from the legal domain. All optimal target solutions, including ties, must recover optimal source solutions. Equal objective values and one-to-one witness mappings are not required. See result mappings.

Turing reductions allow multiple adaptive queries: P → Decision<P> uses binary search over the decision bound.

Witness-mapping implementation

A witness-mapping reduction uses two pieces: a result struct and a ReduceTo<T> impl.

The result struct holds the target problem and the logic to map solutions back:

#[derive(Debug, Clone)]
pub struct ReductionISToVC<W> {
    target: MinimumVertexCover<SimpleGraph, W>,
}

impl<W: WeightElement + VariantParam> ReductionResult for ReductionISToVC<W> {
    type Source = MaximumIndependentSet<SimpleGraph, W>;
    type Target = MinimumVertexCover<SimpleGraph, W>;

    fn target_problem(&self) -> &Self::Target { &self.target }
    fn extract_solution(
        &self,
        target_sol: &Vec<bool>,
    ) -> crate::rules::ExtractionResult<Vec<bool>> {
        crate::rules::traits::validate_target_solution(self.target_problem(), target_sol)?;
        Ok(target_sol.iter().map(|&x| !x).collect())
    }
}

Solution extraction contract

ReductionResult::extract_solution accepts one complete target configuration and returns the source configuration defined by the reduction. Extraction is a fallible boundary, not a recovery mechanism:

1. In every direct extractor, validate once before indexing or decoding. Use validate_target_solution() when decoding needs the evaluated value. Use validate_target_witness(target, solution, certifies_source, message) when the target must certify a source witness. It evaluates once, applies the supplied predicate, and returns ExtractionError on rejection. Keep the rule’s feasibility check or value-map threshold in that predicate. Composed extractors delegate this check.
2. For decision sources, reject an infeasible target value or a failed rule-owned feasibility threshold. Validate structure required by the inverse mapping, such as exactly-one blocks, permutations, paths, flows, or schedules.
3. Apply the reduction’s mathematical inverse once and return a source configuration with the required length and domains.
4. Return ExtractionError when a precondition is not satisfied.

Do not truncate or pad input, substitute zero for missing data, select the first of several invalid candidates, retry with another mapping, or panic on caller-provided configuration data. Empty and singleton instances should flow through the same mathematical mapping unless the reduction itself has a genuine mathematical case distinction.

Zero and sentinel values remain valid when the source model explicitly gives them meaning. For example, MaximumCommonEdgeSubgraph includes an “unmapped” sentinel in its source dimensions. Missing target data must never be interpreted as that sentinel.

Each conditional in an extractor should therefore either reject a named invariant violation or implement a case in the reduction’s mathematics. A normal extractor has one validation phase followed by one decoding phase; it does not accumulate compatibility or fallback branches.

The #[reduction] attribute on the ReduceTo<T> impl registers the reduction in the global registry (via inventory):

#[reduction(transform = exact {
    num_vertices = "num_vertices",
    num_edges = "num_edges",
})]
impl ReduceTo<MinimumVertexCover<SimpleGraph, i64>>
    for MaximumIndependentSet<SimpleGraph, i64>
{
    type Result = ReductionISToVC<i64>;
    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> { /* ... */ }
}

Model size and algorithm limits

Model parameters describe representable input sizes, not a requirement that the number of candidate solutions fit a machine integer. ClosestSubstring and MinimumDiscretePlanarInverseKinematics bound their products of choice counts by the arithmetic mean raised to the number of choices. Database frequency-table consistency uses the largest attribute domain to bound assignment counts. These are complexity upper bounds, not exact per-instance candidate counts.

Database ILP indicator counts and allocation limits are checked when constructing that reduction, not when loading the source model. Source input invariants and its witness representation remain model constraints.

Reduction Graph

Result mappings

Rules follow mathematical contracts, without mandatory category tags. When a target asks whether an objective meets a bound, construct Decision<P>: the target owns the bound and evaluates the predicate; the rule only decodes YES witnesses and maps completed Or answers identically.

Use ReduceTo<T> and ReductionResult::extract_solution for witnesses. When the same construction also maps completed values, implement AggregateReductionResult on its result with #[aggregate_reduction]. The attribute registers the implementation, not a rule category; the implementation owns the mathematical map. Use register_aggregate_reduction!(ResultType) to register concrete instances of generic implementations, including VariantReductionResult<S, T>. Both mappings belong to the same graph edge and share its constructed result. Aggregate-only rules use ReduceToAggregate<T>.

Common maps use an empty implementation:

#[aggregate_reduction(identity)]
impl AggregateReductionResult for ReductionSATToKSAT<K3> {}

#[aggregate_reduction(ilp_feasibility)]
impl AggregateReductionResult for ReductionNAESATToILP {}

The shorthand reuses the ReductionResult source, target, and target accessor. identity returns the value unchanged; ilp_feasibility returns Or(value.value.is_some()). Custom maps keep their explicit implementation. Generic shorthand implementations still need register_aggregate_reduction! for each concrete variant.

ReductionChain::extract_result() recovers completed results using the same library implementation as fixed ILP pipelines. Recovery borrows intermediate instances from the executed chain and requires each extracted witness to realize its mapped aggregate.

Every witness reduction must construct a feasible target whenever the source is feasible. Established target infeasibility therefore implies source infeasibility, without a witness or a value map. This also applies when an intermediate problem is proved infeasible by its completed-value map. For feasible targets, reverse the chain one edge at a time using the required witness and value mappings. Missing required maps, failed extraction, and solver errors are errors, never proof of infeasibility. Completed-result recovery follows the selected solver’s contract, including its numerical tolerances. A witness-only solver API cannot return a witness for a negative decision result and reports that limitation explicitly. These rules do not change Problem, SolutionAggregate, or solver return types.

ReductionGraph::new() reads reduction_entries(), which joins each construction with its registered result mappings, and builds a variant-level directed graph:

• Nodes are unique (problem_name, variant) pairs — e.g., ("MaximumIndependentSet", {graph: "KingsSubgraph", weight: "i64"}).
• Edges come from explicit #[reduction] registrations, including cross-problem and same-problem variant reductions.

Exported files:

• reduction_graph.json — all problem variants and reduction edges
• problem_schemas.json — field definitions for each problem type

These JSON assets are generated during make doc, make mdbook, and make paper; they are build artifacts, not committed source files. Generate them manually with cargo run --example export_graph and cargo run --example export_schemas when you need the raw exports locally.

Path finding

All path-finding operates on exact variant nodes. Use ReductionGraph::variant_to_map(&T::variant()) to convert a Problem::variant() into the required BTreeMap<String, String>.

Each formula has its own relation: exact equality or upper bound. Composition preserves exactness when the formula and its required inputs are exact. Bounded inputs require sound upper-bound substitution. Unavailable fields affect only formulas that depend on them; independent formulas survive. Concrete-instance measurement remains a separate execution API.

Example: Finding a path from MIS{KingsSubgraph, i64} to VC{SimpleGraph, i64}:

MIS{KingsSubgraph,i64} -> MIS{UnitDiskGraph,i64} -> MIS{SimpleGraph,i64} -> VC{SimpleGraph,i64}
    variant reduction        variant reduction              reduction

Executable paths

Execute an explicitly selected path with ReductionGraph::reduce_along_path:

let reduction = graph.reduce_along_path(rpath, &factoring_instance)?.unwrap();
let target: &SpinGlass<SimpleGraph, f64> = reduction.target_problem();
let source_solution = reduction.extract_solution(&target_solution)?;

The returned ReductionChain stores each intermediate reduction and extracts the source solution by applying the inverse mappings in reverse order. Construction returns ReductionError; extraction returns ExtractionError.

#[reduction(
transform = upper_bound {
    num_vars = "num_vertices + num_edges",
    num_clauses = "3 * num_edges",
},
unavailable = {
    encoding_bits = "coefficient magnitudes are not tracked",
},
})]
impl ReduceTo<Target> for Source { ... }

#[reduction(transform = {
    exact { num_vars = "num_vars" },
    upper_bound { num_quadratic_terms = "num_vars * (num_vars - 1) / 2" },
})]
impl ReduceTo<Decision<QUBO<i64>>> for KSatisfiability<K2> { ... }

Input:  ProblemParameters { num_vertices: 10, num_edges: 15 }
Output: ProblemParameters { num_vars: 25 }

Solvers

The reference solver exposes a direct typed operation:

BruteForce::solve(&problem) -> Result<Option<P::Solution>, SolveError>

Some(solution) is a successful exact solve, None means exhaustive search proved infeasibility, and Err reports an operational failure.

ILP results are optimal or infeasible according to HiGHS numerical tolerances; zero MIP gaps do not imply mathematical exactness. Integer extraction rounds variable assignments, validates the original constraints, and recomputes the source objective with checked integer arithmetic. Floating-point objective comparisons in numerical regression tests use an explicit acceptance policy in source units (absolute and relative tolerances of 1e-7 for the QUBO solver regression), separate from the 1e-6 variable-rounding tolerance. This test policy is not a universal bound on backend objective error.

When an ILP target witness misses a source decision threshold, the solver returns ILPSolveError::UnresolvedDecision, not infeasibility: the witness alone cannot prove that no qualifying source solution exists.

JSON Serialization

All problem types support JSON serialization via serde:

use problemreductions::io::{to_json, from_json};

let json: String = to_json(&problem)?;
let restored: MaximumIndependentSet<SimpleGraph, i64> = from_json(&json)?;

QUBO data uses {"num_vars": 3, "entries": [[0,0,-2], [0,1,4]]}. Each entry is [row, column, coefficient] with zero-based indices and row <= column. Output lists only nonzero upper-triangle entries in row-major order. Duplicate, out-of-range, and lower-triangle coordinates are errors. For a lower-triangle coordinate, use (column, row) instead. from_matrix and CLI --matrix still accept full matrices; evaluation and serialization ignore their lower triangle.

Contributing

See the Open Question Board to browse problems and register a problem or solution through a GitHub pull request.