Summary
Add path ranking to pred path (and the matching library and MCP API). Ranking only reorders and annotates the candidates; the user still chooses one explicitly with pred reduce --via. This brings back path selection, which #1137 removed on purpose (MinimizeSteps, Minimize(field), CustomCost). The design below avoids the problems of that version: a "cheapest path" search whose cost doesn't only grow along a path, and a single cost number when sizes are not comparable.
Two modes
Symbolic mode (pred path MIS/i64 QUBO/i64): only the source and target variants are given, with no instance and no parameter values. Each path's composed parameter transform is a formula in the source parameters, so paths are compared as formulas:
- Project each target field's formula with
Growth::from_expr and compare with Growth::dominates (src/growth.rs).
- Output Pareto layers: layer 1 = paths no other path beats, layer 2 = paths beaten only by layer 1, and so on. Comparing over the target's whole parameter vector means no weighting is needed.
- Some paths are incomparable because of missing information: an unavailable field, a Turing step, or
O(?). These go into a separate unrankable group that shows the reason.
- Tie-breaks inside a layer: exact before upper bound, then fewer hops, then the existing canonical order.
Numerical mode (pred path MIS QUBO mis.json): run each path on the instance (#1177, with budget #1178) and measure the actual target parameters. All values are exact u64, so rank with the same Pareto layers. Failed and over-budget paths are reported separately. The symbolic Growth is shown next to each measured path, because a ranking measured on one instance doesn't carry over to other instances.
Objective
- Default: Pareto over the full target parameter vector.
- Optional
--objective "<expr over target parameters>", parsed with Expr::parse, allowing any combination of target fields. It must be monotone, i.e. never decrease as a parameter grows; Growth already assumes and checks this. Reject it otherwise.
- Target complexity strings are too weak to be the default: QUBO's is
O(2^num_vars), which ignores num_quadratic_terms; ILP/i64 is O(?); 85 of 256 variants have O(?).
Candidate generation
Candidates currently come from Yen's k-shortest paths by hop count. Many of them are variant-only detours: 25% of 1,190 sampled candidate paths contain two or more steps that only change the variant (for example MIS SimpleGraph → TriangularSubgraph → UnitDiskGraph → SimpleGraph), and 9% leave a problem and later come back to it. For LCS → ILP, 13 of the top 20 are such detours, and they use up the --limit slots.
Related display bug
Without an instance, the ReductionPath summary line merges consecutive steps with the same problem name. The result is Path (6 steps): MIS → MaxClique → ILP → QUBO, which looks identical to the 4-step path. Output with an instance doesn't merge them, so the two outputs are also inconsistent.
Dependencies
Tasks
Summary
Add path ranking to
pred path(and the matching library and MCP API). Ranking only reorders and annotates the candidates; the user still chooses one explicitly withpred reduce --via. This brings back path selection, which #1137 removed on purpose (MinimizeSteps,Minimize(field),CustomCost). The design below avoids the problems of that version: a "cheapest path" search whose cost doesn't only grow along a path, and a single cost number when sizes are not comparable.Two modes
Symbolic mode (
pred path MIS/i64 QUBO/i64): only the source and target variants are given, with no instance and no parameter values. Each path's composed parameter transform is a formula in the source parameters, so paths are compared as formulas:Growth::from_exprand compare withGrowth::dominates(src/growth.rs).O(?). These go into a separate unrankable group that shows the reason.Numerical mode (
pred path MIS QUBO mis.json): run each path on the instance (#1177, with budget #1178) and measure the actual target parameters. All values are exactu64, so rank with the same Pareto layers. Failed and over-budget paths are reported separately. The symbolicGrowthis shown next to each measured path, because a ranking measured on one instance doesn't carry over to other instances.Objective
--objective "<expr over target parameters>", parsed withExpr::parse, allowing any combination of target fields. It must be monotone, i.e. never decrease as a parameter grows;Growthalready assumes and checks this. Reject it otherwise.O(2^num_vars), which ignoresnum_quadratic_terms; ILP/i64 isO(?); 85 of 256 variants haveO(?).Candidate generation
Candidates currently come from Yen's k-shortest paths by hop count. Many of them are variant-only detours: 25% of 1,190 sampled candidate paths contain two or more steps that only change the variant (for example MIS SimpleGraph → TriangularSubgraph → UnitDiskGraph → SimpleGraph), and 9% leave a problem and later come back to it. For LCS → ILP, 13 of the top 20 are such detours, and they use up the
--limitslots.Related display bug
Without an instance, the
ReductionPathsummary line merges consecutive steps with the same problem name. The result isPath (6 steps): MIS → MaxClique → ILP → QUBO, which looks identical to the 4-step path. Output with an instance doesn't merge them, so the two outputs are also inconsistent.Dependencies
Tasks
Growthper field) or measured, plus Pareto layering with deterministic tie-breaks.--objective.docs/src/design.md, which currently saysGrowth"does not rank or filter paths".