[Bug] QAP→ILP extract_solution produces invalid permutation + non-deterministic reduction path selection

[zazabap]

Summary

Two related bugs cause intermittent CI failures when solving HamiltonianCircuit via ILP:

1. Non-deterministic path selection in the reduction graph (HashMap iteration order)
2. QAP→ILP extract_solution bug producing invalid permutations for certain instances

Bug 1: Non-deterministic path selection

src/rules/graph.rs uses HashMap for node_index and name_to_nodes. Rust's default hasher uses a random seed per process, so the reduction path finder may select different paths across runs:

• Run A: HC → TSP → ILP (correct)
• Run B: HC → QAP → ILP (triggers Bug 2)

Both paths have similar overhead, so which is chosen depends on HashMap iteration order.

Fix options:

• Replace HashMap with BTreeMap for deterministic iteration
• Add path selection tiebreaking (prefer shorter/simpler paths)

Bug 2: QAP→ILP extraction produces invalid permutation

When the reduction graph selects HC → QAP → ILP for the prism graph (6 vertices, 9 edges), the QAP→ILP extract_solution (src/rules/quadraticassignment_ilp.rs:37-46) returns permutation [1, 2, 3, 0, 5, 4]. This represents tour 1→2→3→0→5→4→1, but edge (2,3) does not exist in the prism graph — so this is NOT a valid Hamiltonian circuit.

The QAP→ILP reduction uses McCormick linearization for z_{ijpq} = x_{ip} * x_{jq}. While McCormick is theoretically exact for binary variables, the resulting ILP has 1332 variables (36 x-vars + 1296 z-vars) for n=6. HiGHS may encounter numerical issues in branch-and-bound that lead to an incorrect extraction.

Specific investigation needed:

• Does HiGHS return a truly optimal ILP solution, or does it return a solution that violates integrality tolerances?
• Are the McCormick constraints properly tightened? (e.g., missing z >= 0 lower bound?)
• Does the QAP evaluate() confirm the extracted permutation is suboptimal?

Reproduction

# The test passes locally but fails on some HashMap seeds.
# To reproduce, run repeatedly — it depends on HashMap random seed:
cargo test --features "ilp-highs example-db" -- model_specs_are_optimal

The failure is intermittent locally but was consistent on CI during PR #779.

Workaround applied

PR #779 changed the HC model example from the prism graph to K4 (complete graph on 4 vertices), where every permutation is a valid HC. This makes the test pass regardless of which reduction path is selected or what permutation the solver extracts.

Files involved

• src/rules/graph.rs — HashMap-based reduction graph (Bug 1)
• src/rules/quadraticassignment_ilp.rs — QAP→ILP reduction + extraction (Bug 2)
• src/rules/ilp_helpers.rs — mccormick_product helper
• src/models/graph/hamiltonian_circuit.rs — model example spec (workaround applied)