Getting started

cargo add problemreductions

The library includes the HiGHS ILP backend.

Solve a small instance

use problemreductions::prelude::*;

fn main() {
    let problem = MaximumSetPacking::<i64>::new(vec![
        vec![0, 1], vec![1, 2], vec![2, 3], vec![4, 5],
    ]);
    let solver = BruteForce::new();
    let solution = solver.solve(&problem).unwrap().unwrap();
    println!("{:?}: {}", solution, problem.evaluate(&solution).unwrap());
}

The optimal packing selects sets 0, 2, and 3: the witness is [true, false, true, true] and evaluates to Max(3). Problem::evaluate scores a configuration; BruteForce enumerates the configuration space, so keep exhaustive examples small.

Apply a reduction

Reduce the same instance to binary ILP, solve the target, and recover the original configuration:

use problemreductions::prelude::*;
use problemreductions::models::algebraic::ILP;
use problemreductions::solvers::ILPSolver;

fn main() {
    let problem = MaximumSetPacking::<i64>::new(vec![
        vec![0, 1], vec![1, 2], vec![2, 3], vec![4, 5],
    ]);
    let reduction = ReduceTo::<ILP<bool>>::reduce_to(&problem).unwrap();
    let target = reduction.target_problem();
    assert_eq!(target.num_vars(), 4);
    assert_eq!(target.num_constraints(), 2);

    let target_solution = ILPSolver::new().solve(target).unwrap();
    let solution = reduction.extract_solution(&target_solution).unwrap();
    assert_eq!(solution, vec![true, false, true, true]);
    println!("{}", problem.evaluate(&solution).unwrap()); // Max(3)
}

The target has one binary variable per set and a constraint for each element shared by multiple sets. extract_solution maps a target solution back to the source solution type. ILPSolver::new().solve(&problem) executes the exact variant’s registered ILP pipeline and returns its source solution.

Discover and run a path

Search uses exact variants. This discovers a route from Factoring to SpinGlass and executes it:

use problemreductions::models::algebraic::ILP;
use problemreductions::prelude::*;
use problemreductions::rules::{ReductionGraph, ReductionMode};
use problemreductions::solvers::ILPSolver;
use problemreductions::topology::SimpleGraph;
    let graph = ReductionGraph::new(); // all registered reductions
    let src_var = ReductionGraph::variant_to_map(&Factoring::variant()); // {} (no variant params)
    let dst_var = ReductionGraph::variant_to_map(&SpinGlass::<SimpleGraph, f64>::variant()); // {graph: "SimpleGraph", weight: "f64"}
    let paths = graph.find_all_paths_mode(
        "Factoring",
        &src_var,
        "SpinGlass",
        &dst_var,
        ReductionMode::Witness,
    );
    let rpath = paths
        .iter()
        .find(|path| path.type_names() == ["Factoring", "CircuitSAT", "SpinGlass"])
        .expect("explicit Factoring -> CircuitSAT -> SpinGlass route");
    println!("  {}", rpath);
    let factoring = Factoring::with_factor_bits(
        6, // target_product:  find p × q = 6
        2, // num_bits_first:  p is a 2-bit factor
        2, // num_bits_second: q is a 2-bit factor
    );

let reduction = graph.reduce_along_path(rpath, &factoring).unwrap().unwrap();
let target: &SpinGlass<SimpleGraph, f64> = reduction.target_problem();
// Solve `target`, then call reduction.extract_solution(&target_solution).

extract_solution walks the intermediate mappings in reverse. The full example also solves factoring through a direct ILP reduction and checks that the recovered factors multiply to 6:

cargo run --example chained_reduction_factoring_to_spinglass

Solver contracts

Every successful solve returns the problem's Solution. Evaluate it against the source with Problem::evaluate, which returns Result<P::Value, EvaluationError>. Path discovery enumerates routes; it does not rank them or register a solver capability. See the solver API.