Make `pred solve` deterministic through registered solver pipelines

[isPANN]

Background

pred solve is a core operation that will be called frequently by users and other APIs. For the same valid input and options, it must follow the same execution path and return the same result.

Reduction-path search is different: the graph may contain many routes, search policies and limits affect which route is found, and new reduction rules can change the result. That uncertainty is appropriate for the exploratory pred path and explicit pred reduce features, but it must not be hidden inside pred solve. A solver may still execute a multi-hop route when that exact route is registered in advance as one deterministic solver pipeline.

Why this separation matters

Solving must be predictable and reproducible; path search is an optional expansion feature. The relevant boundary is not one hop versus many hops. It is runtime discovery versus execution of a pre-registered fixed process. Keeping those separate guarantees that adding an unrelated reduction edge cannot silently change how a problem is solved, which pipeline runs, or which solution is returned.

The product boundary is:

pred solve          deterministic dispatch; executes a registered solver/pipeline
pred path/reduce    explicit reduction-graph exploration and transformation

Objective

Make pred solve a fully deterministic process backed by exact-variant solver capabilities.

For a given package version, normalized input, and explicit options, repeated calls must return the same:

• selected solver class;
• feasibility status and objective value;
• witness/configuration when one exists;
• error class when solving fails.

Exact-variant capabilities

Each canonical problem name plus fully normalized variant map has the equivalent of:

struct SolverCapabilities {
    native: Option<NativeSolverRegistration>,
    ilp: Option<IlpPipelineRegistration>,
}

Required rules:

1. An exact variant has at most one native solver and at most one ILP pipeline.
2. Duplicate registrations are rejected; registration order never chooses a winner.
3. Registrations are never inherited or borrowed across variants.
4. A registered native solver must handle every valid instance of its exact variant. It cannot return NotApplicable.
5. A registered ILP pipeline must handle every valid instance of its exact source variant and end at a supported ILP variant.
6. Brute-force is universally available and does not require per-problem registration.
7. There are no numeric priorities, runtime benchmarks, portfolios, or configurable ordering.
8. An ILP pipeline fixes its complete ordered sequence of problem names, exact variants, witness-capable reductions, and solution extractors at registration time. Its length may be one or many hops.
9. Runtime solver dispatch executes the registered pipeline verbatim. It never asks the reduction graph to discover or replace any step.

Deterministic default dispatch

The default order is fixed:

native > registered ILP pipeline > brute-force

All library, CLI, and MCP callers use one shared resolver:

capabilities = registry.lookup(exact_problem_key)

if capabilities.native exists:
    return native.solve(instance)

if capabilities.ilp exists:
    execute the registered fixed reduction pipeline
    solve its final ILP
    map the solution back through the registered extractors
    return result

return brute_force.solve(instance)

Once a solver is selected, timeout, infeasibility, or execution failure is returned directly. The dispatcher does not retry with another solver.

The resolver must not query ReductionGraph, enumerate candidate paths, or use exact/approximate search policies. Executing the already registered steps of an ILP pipeline is allowed and required.

Deterministic solutions

For a fixed package version, normalized input, and solver selection, repeated executions must return the same witness. Each native backend, registered ILP pipeline, and brute-force implementation must therefore use deterministic execution and tie-breaking; incidental randomness, parallel discovery order, or unstable iteration order must not affect the public result.

Different solver classes are not required to choose the same witness when several optimal witnesses exist. Native, ILP, and brute-force may return different witnesses as long as every returned witness is valid and they agree on feasibility and the optimal objective value.

Explicit solver overrides

The only public solver inputs are:

--solver ilp
--solver brute-force

Their behavior is fixed:

• --solver ilp: require the exact variant's registered ILP pipeline; otherwise return a capability error. Execute that pipeline exactly; never search or fall back.
• --solver brute-force: bypass native and ILP and run brute-force.
• omitted --solver / omitted MCP solver: use the fixed default dispatch above.

These are not accepted solver values:

auto
customized
native
<native-implementation-id>

auto describes omission behavior, not a solver. Native implementation IDs are diagnostic metadata, not public selectors.

Output contract

The existing top-level solve result remains intact except that solver becomes an execution-information object. Its kind is always native, ilp, or brute-force; it is never auto or customized:

{"solver": {"kind": "native", "implementation": "fd-subset-search"}}
{"solver": {"kind": "ilp", "reduction_path": ["MaximumIndependentSet<SimpleGraph, One>", "MaximumIndependentSet<SimpleGraph, i32>", "MaximumClique<SimpleGraph, i32>", "ILP<bool>"]}}
{"solver": {"kind": "brute-force"}}

Native results report the registered implementation ID. ILP results report the exact fixed reduction path that was executed; a problem already expressed as a supported ILP reports a one-node path. Brute-force has no additional execution metadata. There is no separate pipeline ID.

The old top-level reduced_to field is removed because the ILP solver object already carries the complete execution path. No other solve-result fields are redesigned by this issue.

pred inspect and MCP inspect_problem must expose the same capabilities, computed default solver, native implementation metadata, and registered ILP reduction path. A reduction bundle resolves a solver for its already-constructed target only and then maps the solution back; it never continues path search.

Capability errors describe registration, not graph topology:

No ILP pipeline is registered for MaximumIndependentSet<SimpleGraph, One>

Registration and migration

• A witness-capable direct ReduceTo<ILP<_>> declaration may register a one-hop ILP pipeline for its exact source variant.
• A multi-hop ILP pipeline is registered explicitly as one ordered composition of existing witness-capable reductions. Registration stores or generates its executable reducer/extractor composition; runtime solving does not reconstruct it through graph search.
• Pipeline registration validates every adjacent exact variant, witness-capable reduction, final ILP type, and reverse solution mapping. An invalid registered pipeline is a deterministic registry-construction error.
• The same reduction implementations remain usable by explicit pred path / pred reduce, so pipeline registration composes existing code rather than duplicating formulations.
• Delete the centralized CustomizedSolver::supports_problem / solve_dyn downcast chain.
• Register its existing problem-specific algorithms as native solvers for their exact variants: MinimumCardinalityKey, AdditionalKey, PrimeAttributeName, BoyceCoddNormalFormViolation, PartialFeedbackEdgeSet<SimpleGraph>, and RootedTreeArrangement<SimpleGraph>.
• Keep brute-force as the generic fallback rather than registering it once per problem.

Concrete behavior

Exact problem state	Default	--solver ilp	--solver brute-force
Native and ILP pipeline registered	native	registered ILP pipeline	brute-force
Only ILP pipeline registered	registered ILP pipeline	registered ILP pipeline	brute-force
No ILP pipeline registered, even if a multi-hop ILP path exists in the graph	brute-force	capability error	brute-force

Examples:

• MinimumCardinalityKey defaults to its registered native solver.
• MaximumClique<SimpleGraph, i32> defaults to its registered one-hop ILP pipeline when no native solver exists.
• MaximumIndependentSet<SimpleGraph, One> may register the fixed multi-hop pipeline MIS<One> -> MIS<i32> -> MaximumClique<i32> -> ILP<bool> and then deterministically default to ILP.
• HamiltonianCircuit<SimpleGraph> defaults to brute-force if it has graph routes to ILP but none of those exact routes is registered as its ILP pipeline.
• Registering a fixed one-hop or multi-hop pipeline changes default solving to ILP; merely adding another reduction edge or discoverable route does not.

Verification

Add focused tests so a cold reviewer can run:

cargo test -p problemreductions solver_capability_registry --features ilp-highs
cargo test -p problemreductions-cli deterministic_solver_dispatch --features mcp
make check

The tests must prove:

1. The same serialized instance solved repeatedly through library, CLI, and MCP selects the same solver and returns byte-for-byte equal status, value, and witness fields.
2. A problem with multiple optimal witnesses is deterministic when repeated through each solver class; different solver classes may choose different valid optimal witnesses but must agree on feasibility and optimal objective value.
3. A variant with both registrations defaults to native; explicit ILP executes the registered pipeline; explicit brute-force executes brute-force.
4. A variant with a registered multi-hop ILP pipeline executes exactly the declared nodes/reductions in order and returns the same mapped-back witness on repeated runs.
5. A variant with no ILP pipeline but a known graph route defaults to brute-force; explicit ILP returns a capability error.
6. Adding a test-only reduction edge does not change the registered pipeline, default solver selection, or returned witness.
7. Duplicate or structurally invalid pipeline registrations are rejected and registrations do not leak across variants.
8. Timeout, infeasibility, and solver errors are returned without fallback.
9. CLI and MCP reject auto, customized, native, and native implementation IDs as solver inputs.
10. At least one former CustomizedSolver problem solves through its native registration and reports solver: native plus its implementation ID.

This architectural guard must print no matches, while the behavioral tests above still pass:

rg 'find_.*path|CustomizedSolver' src/solvers problemreductions-cli/src/dispatch.rs problemreductions-cli/src/commands/solve.rs

Out of scope

• Automatically turning arbitrary graph paths into solver pipelines.
• Multiple native solvers for one exact variant.
• Priority configuration, benchmark-based routing, or portfolio solving.
• Changing explicit pred path or pred reduce semantics.