Getting Started

What This Library Does

problem-reductions transforms hard computational problems into forms that efficient solvers can handle. You define a problem, reduce it to another problem type (like QUBO or ILP), solve the reduced problem, and extract the solution back. The interactive reduction graph shows all available problem types and transformations.

Installation

Add to your Cargo.toml:

[dependencies]
problemreductions = "0.2"

The Reduction Workflow

The core workflow is: create a problem, reduce it to a target, solve the target, and extract the solution back.

Example 1: Direct reduction — Set Packing to ILP

Reduce Maximum Set Packing to Integer Linear Programming (ILP), solve with the ILP solver, and extract the solution back.

Step 1 — Create the source problem

A small set system with pairwise overlaps gives a direct binary ILP.

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

let problem = MaximumSetPacking::<i32>::new(vec![
    vec![0, 1],
    vec![1, 2],
    vec![2, 3],
    vec![4, 5],
]);

Step 2 — Reduce to ILP

ReduceTo applies a single-step reduction. The result holds the target problem and knows how to map solutions back. The ILP formulation introduces binary variable x_i for each set, constraint x_i + x_j ≤ 1 for each overlapping pair, and maximizes the weighted sum.

let reduction = ReduceTo::<ILP>::reduce_to(&problem);
let ilp = reduction.target_problem();
println!("ILP: {} variables, {} constraints", ilp.num_vars, ilp.constraints.len());

ILP: 4 variables, 2 constraints

Step 3 — Solve the ILP

ILPSolver uses the HiGHS solver to find optimal solutions efficiently. For small instances you can also use BruteForce, but ILPSolver scales to much larger problems.

let solver = ILPSolver::new();
let ilp_solution = solver.solve(ilp).unwrap();
println!("ILP solution: {:?}", ilp_solution);

ILP solution: [1, 0, 1, 0]

Step 4 — Extract and verify

extract_solution maps the ILP solution back to the original problem's configuration space.

let solution = reduction.extract_solution(&ilp_solution);
let metric = problem.evaluate(&solution);
println!("Packing solution: {:?} -> size {:?}", solution, metric);
assert!(metric.is_valid());

Packing solution: [1, 0, 1, 1] -> size Valid(3)

For convenience, ILPSolver::solve_reduced combines reduce + solve + extract in a single call:

let solution = ILPSolver::new().solve_reduced(&problem).unwrap();
assert!(problem.evaluate(&solution).is_valid());

Example 2: Reduction path search — integer factoring to spin glass

Real-world problems often require chaining multiple reductions. Here we factor the integer 6 by reducing Factoring through the reduction graph to SpinGlass, through automatic reduction path search. (full source)

Let's walk through each step.

Step 1 — Discover the reduction path

ReductionGraph holds every registered reduction. find_cheapest_path searches for the shortest chain from a source problem variant to a target variant.

    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 rpath = graph
        .find_cheapest_path(
            "Factoring",               // source problem name
            &src_var,                  // source variant map
            "SpinGlass",               // target problem name
            &dst_var,                  // target variant map
            &ProblemSize::new(vec![]), // input size (empty = unknown)
            &MinimizeSteps,            // cost function: fewest hops
        )
        .unwrap();
    println!("  {}", rpath);

  Factoring → CircuitSAT → SpinGlass {graph: "SimpleGraph", weight: "i32"}

Step 2 — Create the Factoring problem

Factoring::new(m, n, target) creates a factoring instance: find two factors p (m-bit) and q (n-bit) such that p × q = target. Here we factor 6 with two 2-bit factors, expecting 2 × 3 or 3 × 2.

    let factoring = Factoring::new(
        2, // num_bits_first:  p is a 2-bit factor
        2, // num_bits_second: q is a 2-bit factor
        6, // target_product:  find p × q = 6
    );

Step 3 — Solve with ILPSolver

solve_reduced reduces the problem to ILP internally and solves it in one call. It returns a configuration vector for the original problem — no manual extraction needed. For small instances you can also use BruteForce, but ILPSolver scales to much larger problems.

    // Factoring reduces to ILP<i32>, so we manually reduce, solve, and extract
    let solver = ILPSolver::new();
    let reduction = ReduceTo::<ILP<i32>>::reduce_to(&factoring);
    let ilp_solution = solver.solve(reduction.target_problem()).unwrap();
    let solution = reduction.extract_solution(&ilp_solution);

Step 4 — Read and verify the factors

read_factors decodes the binary configuration back into the two integer factors.

    let (p, q) = factoring.read_factors(&solution); // decode bit assignments → integers
    println!("{} = {} × {}", factoring.target(), p, q);
    assert_eq!(p * q, 6, "Factors should multiply to 6");

6 = 3 × 2

Step 5 — Inspect the overhead

Each reduction edge carries a polynomial overhead mapping source problem sizes to target sizes. path_overheads returns the per-edge polynomials, and compose_path_overhead composes them symbolically into a single end-to-end formula.

    // Print per-edge overhead polynomials
    let edge_overheads = graph.path_overheads(&rpath);
    for (i, overhead) in edge_overheads.iter().enumerate() {
        println!("{} → {}:", rpath.steps[i], rpath.steps[i + 1]);
        for (field, poly) in &overhead.output_size {
            println!("  {} = {}", field, poly);
        }
    }

    // Compose overheads symbolically along the full path
    let composed = graph.compose_path_overhead(&rpath);
    println!("Composed (source → target):");
    for (field, poly) in &composed.output_size {
        println!("  {} = {}", field, poly);
    }

Factoring → CircuitSAT:
  num_variables = num_bits_first * num_bits_second
  num_assignments = num_bits_first * num_bits_second
CircuitSAT → SpinGlass {graph: "SimpleGraph", weight: "i32"}:
  num_spins = num_assignments
  num_interactions = num_assignments
SpinGlass {graph: "SimpleGraph", weight: "i32"} → SpinGlass {graph: "SimpleGraph", weight: "f64"}:
  num_spins = num_spins
  num_interactions = num_interactions
Composed (source → target):
  num_spins = num_bits_first * num_bits_second
  num_interactions = num_bits_first * num_bits_second

Solvers

Two solvers are available:

ILP support is enabled by default. To disable it:

[dependencies]
problemreductions = { version = "0.2", default-features = false }

JSON Resources

The library exports machine-readable metadata useful for tooling and research:

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

Next Steps

• Try the CLI tool to explore problems and reduction paths from your terminal
• Explore the interactive reduction graph to discover available reductions
• Read the Design guide for implementation details
• Browse the API Reference for full documentation