python-hypergraph-treewidth-dp-robust-scheduling-20261011
I diagnosed the class of failure modes and built a complete, verified reference implementation. The full self-contained markdown deliverable is at ~/SOLUTION.md, with the tested source files at ~/solver.py and ~/test_solver.py.
SOLUTION.md (1093 lines) containing: title, root-cause analysis, the exact fix (full solver.py + test_solver.py embedded), and a verification section with observed output.
| # | Failure mode | Fix |
|---|---|---|
| RC1 | Width cap checked after DP state allocation → corrupted partial tables | validate_decomposition() is pure/read-only and runs first; raises WidthCapExceeded before any _DP object exists |
| RC2 | Global machine limit treated as a bag-local constraint → invisible cross-branch overlap | Machine limit = Hyperedge(all jobs, M); validation requires every hyperedge to fit a bag, else reject |
| RC3 | Disconnected components dropped/crash | Builder computes components and joins their trees under an empty connector bag |
| RC4 | Ties resolved by hash/set order | Bags sorted, canonical bag by (depth,index), arg-min key (cost, assignment_tuple) → lexicographically smallest |
| RC5 | Only scalar optimum, no schedule | DP tables retained; deterministic top-down backtrack; independent evaluate() re-checks |
| RC6 | Invalid decompositions silently accepted | Full validation: coverage, tree, running intersection, precedence/hyperedge containment |
Exact junction-tree message passing over the supplied decomposition. For bag B_u, DP_u[assignment] = min subtree cost, charging each job's tardiness at its unique forget node and each constraint at a canonical bag; children merged by minimizing over private vertices while agreeing on B_u ∩ B_child. Cost is O(m · H^(tw+1)) with H = sum(p).
$ python3 test_solver.py
brute-force equivalence: 380 instances OK
disconnected components: OK
global machine limit: OK
width-cap rejection atomicity: OK
invalid decomposition detection: OK
deterministic tie-breaking: OK
horizon adequacy (extra idle slack): OK
independent infeasibility checker: OK
ALL TESTS PASSED
Independent cross-checks against exhaustive brute force:
- M=1, 4 unit jobs, due 0 → cost 10.0, start [0,1,2,3]
- M=2 → cost 6.0, start [0,0,1,1]
- precedence 0→1→2→3 on 2 machines → cost 10.0
- extended random suite: 109 more instances OK
- chain n=30, width 2 → feasible reconstruction, cost 1363.0
Self-containment verified: I extracted the fenced code from SOLUTION.md into a clean temp directory, confirmed both embedded blocks are byte-identical to the tested files, and re-ran the suite there — exit 0, ALL TESTS PASSED.
The width-cap rejection is atomic (WidthCapExceeded carries .width/.cap; instance and decomposition remain unchanged and a later legal solve succeeds), and all tie-breaking is deterministic.
# Evidence - Problem class: python-hypergraph-treewidth-dp-robust-scheduling-20261011 - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-12T04:08:35.508Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Given a large sparse constraint hypergraph and precedence-constrained jobs, design an exact solver using tree-decomposition dynamic programming to minimize weighted tardiness under machine and resource limits. The implementation must reconstruct an optimal schedule, handle disconnected components and ties deterministically, and reject decompositions whose width exceeds a supplied cap without corrupting partial results.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-hypergraph-treewidth-dp-robust-scheduling-20261011", "provider": "openrouter", "solved_at": "2026-10-12T04:08:35.508Z", "version": "3.11"}