[Solver] Repair nine partial ILP routes currently falling back to brute force

[isPANN]

Background

PR #1091 makes solve deterministic: an exact problem variant uses a registered native solver, then a registered fixed reduction-to-ILP pipeline, and otherwise brute force. During migration we found nine variants for which graph search can discover a route to ILP, but at least one reduction in that route is only defined for a subset of the source model's valid input domain. Registering such a route would make solve panic or reject otherwise valid instances, so these variants intentionally remain on brute force for now.

This is a reduction-contract problem, not a path-search problem. ReduceTo<T> is a total interface: if the source constructor accepts an instance, reduce_to() must construct a target and preserve feasibility/objective and witness extraction for that instance.

Objective

Repair the partial mappings below so every valid instance of each exact source variant has a sound, executable fixed pipeline to ILP<bool> or ILP<i32>, then register those pipelines for deterministic solving. Do not restore runtime path search or make solver dispatch depend on instance values.

Interface (Input → Output)

In: any valid instance of one of the nine exact variants below.

Out: a total reduction-to-ILP pipeline whose ILP optimum/feasibility and extracted witness agree with the source problem; both default dispatch and an explicit ILP request execute that registered pipeline. Until each mapping is repaired, the current brute-force fallback is the safe behavior.

Affected mappings

1. ClosestVectorProblem<i32> → QUBO<f64> → ILP<bool>
ClosestVectorProblem<i32> permits bounds without a finite lower endpoint, while the QUBO reduction requires every lower bound to be finite.

2. IntegerKnapsack → ILP<i32>
   Valid instances may require multiplicities greater than i32::MAX; the current reduction rejects them.

3. MaxCut<SimpleGraph, i32> → MinimumMatrixCover → ILP<bool>
MaxCut<i32> permits negative edge weights, while the first reduction requires nonnegative weights.

4. MinimumFeedbackArcSet<i32> → MaximumLikelihoodRanking → ILP<bool>
   The source permits arbitrary integer arc weights, while the first reduction requires unit weights.

5. PrizeCollectingSteinerForest<SimpleGraph, i32> → SteinerTree<SimpleGraph, i32> → ILP<bool>
   The first reduction creates zero-weight gadget edges, while SteinerTree → ILP requires strictly positive edge weights. The canonical reference route currently fails during construction for this reason.

6. SequencingToMinimizeWeightedCompletionTime → ILP<i32>
   Processing times and weights are u64 and may exceed the exact ILP<i32> / f64 encoding range.

7. SteinerTree<SimpleGraph, i32> → ILP<bool>
   The source accepts zero and negative edge weights, while the ILP reduction requires strictly positive weights.

8. SteinerTreeInGraphs<SimpleGraph, i32> → ILP<bool>
   The source accepts zero and negative edge weights, while the ILP reduction requires strictly positive weights.

9. SubsetSum → ClosestVectorProblem<i32> → QUBO<f64> → ILP<bool>
SubsetSum permits u64 sizes and targets outside the i32 range, while the first reduction rejects them.

Technical recommendations

• Treat the nine items as explicit follow-up checkboxes or split them into per-rule child issues during implementation; do not hide partiality behind catch_unwind, instance-dependent capability checks, or fallback after a selected backend fails.
• Prefer total encodings over narrowing existing model domains. If a model-domain change is mathematically necessary, document it as a deliberate API change and validate it at construction/deserialization boundaries.
• Stop each registered pipeline at the first directly supported ILP<bool> or ILP<i32> node.
• Keep the fixed solver registry exact-variant based. A pipeline may be registered only after its whole source variant is supported.

Verification

Add a focused regression module and run:

cargo test --lib partial_ilp_routes --features ilp-highs -- --nocapture

The output must report nine passing boundary-case tests, one per mapping above. Each test must:

1. construct a valid instance exercising the currently unsupported boundary (unbounded-lower CVP bound, multiplicity above i32::MAX, negative/non-unit/zero weights, or values outside the exact integer encoding range);
2. run the full registered pipeline without panic;
3. check target feasibility/objective and extracted source witness against a hand-checkable expected result or independent brute-force result where the configuration space is tractable; and
4. assert that solver_capabilities(exact_key).ilp is present and deterministic default dispatch reports SolverExecution::Ilp.

These boundary instances are the negative controls: with the current partial reductions, each test must fail by rejection/panic or by observing no registered ILP capability. A test using only the existing small canonical examples is insufficient because those examples already avoid the broken parts of the input domains.

Finally run make check; it must pass without changing dispatch to search dynamically or fall back after a selected ILP backend fails.

Out of scope

• Restoring path search inside solve.
• Registering an ILP pipeline that is valid only for selected instances of an exact variant.
• Committing the local migration snapshot as a permanent public route contract.