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
Summary
best_path_to_ilpusesMinimizeStepsThenOverheadwithSTEP_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):
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
MinimizeStepsThenOverheadassigns1e9per 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
Related