[Enhancement] ILP path selector over-prioritizes step count over final output size #788
Description
Summary
best_path_to_ilp uses MinimizeStepsThenOverhead with STEP_WEIGHT = 1e9, which makes step count absolutely dominate. This causes it to miss shorter-ILP paths that have more reduction steps.
Example
For HamiltonianCircuit on the prism graph (6 vertices, 9 edges):
| Path | Steps | Final ILP total |
|---|---|---|
| HC → HP → C1S → ILP<bool> | 3 | 60 |
| HC → RuralPostman → ILP<i32> | 2 | 366 ← currently selected |
| HC → TSP → ILP<bool> | 2 | 768 |
| HC → HP → ILP<bool> | 2 | 1260 |
| HC → QAP → ILP<bool> | 2 | 5232 |
The 3-step C1S path produces a 6× smaller ILP than the selected 2-step RuralPostman path. For ILP solving, the final problem size dominates runtime — reduction steps are negligible.
Current behavior
MinimizeStepsThenOverhead assigns 1e9 per step, so a 3-step path (cost ≥ 3e9) can never beat a 2-step path (cost ≤ 2e9 + overhead), regardless of final ILP size.
Desired behavior
The path selector should prefer paths that produce the smallest final ILP, even if they have more reduction steps.
Constraints
- Dijkstra requires additive edge costs, but "minimize composed final output" is not additive
- Enumerating all paths is exponential and will not scale as the reduction graph grows
- A simple, correct-enough heuristic is preferred over an optimal but complex solution
Related
- PR feat: overhead-aware ILP path selection (fixes #780) #785: introduced overhead-aware path selection (fixes the QAP non-determinism issue)
- Issue [Bug] QAP→ILP extract_solution produces invalid permutation + non-deterministic reduction path selection #780: original bug report