v0.2.0

The first release with library changes since 0.1.1. Nothing public was removed or renamed, so 0.1.2 code compiles unchanged, but the default portfolio is a different solver: new constructions, the whole budget spent, and a decomposition returned on graphs where 0.1.2 returned nothing.

Solver comparison

On the 9,413 selected component graphs from Model Counting Competition formulas, ten seconds each on one CPU, every baseline at the setting its own documentation recommends (#53): goatd is exact best on 9,213 (97.9%) and within one of the best width on 9,298 (98.8%), with a nontrivial decomposition on 9,347 (99.3%). The 0.1.2 table covered 6,640 graphs under an older accounting and is not comparable (#32, #33). "Exact best" is the smallest width among the displayed solvers, not a proven optimum.

What the default portfolio does now

• Spends its whole budget: restarts run to the deadline and a large residual gets the second half of the window when FlowCutter declines it (#48, #52, #56, #60, #62, #63).
• Returns a decomposition on large graphs: a candidate stopped at the soft budget is kept, remaining components are ordered against the hard deadline, and the first candidate runs on the preprocessed residual like every other (#47, #49, #61).
• Hedges on graph coordinates: the tie-weighted candidates run again on an eccentricity ranking from an embedding (#43, #45).
• Samples restarts from a band of near-minimal vertices instead of the exact tie set (#50), and picks its schedule from the residual size and the budget rather than a fixed vertex count (#51, #59).
• Adds maximum-cardinality and minimal-triangulation orders, drops the winner's unnecessary fill (#57), and lifts bipartite graphs through one side (#70).
• Works on the decompositions already built: recombination over the pooled bags, a merge stage, and a re-triangulation between pooled trees (#71, #73).
• Ends with relative fill and a vertex reinsertion pass that rebuilds each vertex's attachment and keeps the result only when it is narrower or lighter (#81, #82); the pass now gets an eighth of the hard window, a round gate priced on what a completion costs, and a cycle that continues past an improvement (#83).
• Nested dissection stops at its deadline instead of running past it (#71).

Opt-in and off by default: PortfolioConfig::with_sampling_patience, which ends stalled restarts early at a cost in width (#67), and TreeDecomposition::new_trusted, which skips release-build validation for a decomposition the caller trusts (#75).

Command line

• New portfolio flags: --hard-budget, --trace, --no-hedge, --hedge-dims, --hedge-random, --hedge-reserve, --capped-restarts, --sample-band, --sample-band-alternate, --expensive-orders-up-to, --mcs-up-to, --no-mcs, --mcsm-up-to, --no-mcsm, --drop-fill-up-to, --no-drop-fill, --sampling-patience, --no-sampling-patience, --no-bipartite-lift, --bipartite-lift-rate, --recombine-up-to, --no-recombine, --merge-up-to, --no-merge, --local-merge-up-to, --no-local-merge; --order merge-loop runs the merge construction on its own (#34 through #73).
• --trace prints each candidate's stage, pass, seed, width, time, bag mass and widest separator (#43, #65, #68).
• On Unix the tool installs a SIGTERM handler and writes the decomposition it holds when a harness stops it (#52).
• A flag that decides nothing for the chosen order is a usage error naming the flag and the order it needs (#72).

Library API

Nothing public was removed or renamed. New:

• stop_flag() at the crate root: store true to end a running solve and take the best decomposition so far (#52).
• The embedding module (#43, #45).
• portfolio::decompose_traced and candidates_traced, with Candidate, CandidateOrigin, CandidateOutcome, CandidateTrace, Pass, Shape, Stage (#43, #65, #68).
• PortfolioConfig builders for every stage above, including standard_with_budget and with_hard_budget; Hedge, HedgeSeries, HedgeWeights, SamplingPatience and their constants (#41 through #73).
• elimination::Order::{RelativeFill, MaximumCardinality, MinimalTriangulation, FillDegreeSampled}; the enum is #[non_exhaustive] (#35, #57, #81).
• decomposition::minimalize_triangulation, decomposition::decompose_by_merging, decomposition::vertex_rebuild::{improve, improve_trusted, Stats} (#57, #71, #81).
• TreeDecomposition::new_trusted and TreeDecomposition::write_td (#75, #37); flowcutter::Budget::standalone (#22).

Changed behaviour: portfolio::candidates and sampled_min_fill_candidates return compacted decompositions sorted on the compacted key, so the head of the list is what decompose returns (#65). PortfolioConfig::standard() leaves the pooled stages off because they need a window; a caller with a time share per graph wants standard_with_budget(share / 2).with_hard_budget(share) (#48, #70, #71).

Correctness fixes

• Minimum-degree heap entries were corrected only on reaching the top of the heap (#46).
• A sampled elimination stopped by the hard deadline could return a vertex in no bag (#64).
• Recombination could select a cap holding vertices outside its block (#77).
• Incremental min-fill maintenance repaired; interrupted residuals complete with bounded output (#34).

Performance

With output unchanged: linear-time validation and construction, 28 s to 25 ms on a 92,100-vertex graph (#74); faster PACE parsing and output (#37); sampled min-fill hot paths (#38); min-degree on dense residuals through a bucket queue (#66); fewer allocations in FlowCutter, the partitioner, validation and the embedding (#72, #76, #78); the elimination core updates fill counts from the edges an elimination adds, ten times more restarts inside a budget on a 5,614-vertex graph (#79); fixed per-restart costs on graphs of 100,000 to 4.5 million vertices halved (#80); reinsertion rebuilds share one completion and a witness store, and a rebuild copies and sorts nothing it keeps, halving the pass's wall twice over (#82, #83).

Bindings and artifacts

• Python: pip install goatd, wheels for CPython 3.10 and later on Linux x86-64, macOS arm64 and Windows x64; elsewhere pip builds from the source distribution with a Rust toolchain and a C++20 compiler.
• C and C++: a goatd-c-v0.2.0-<target> archive per platform with the header, the shared and static libraries and the notices. No API change (#22).
• WebAssembly: new, bindings/wasm/; the solver page built from it runs at https://tractables.github.io/goatd/ (#24, #26, #31).
• Command line: archives for the three platforms with sha256 files. The Linux binary needs glibc 2.34 or newer.

Compatibility

Minimum supported Rust version 1.88, unchanged. The binary gains a libc dependency on Unix for its SIGTERM handler; the library makes no platform calls and stays single-threaded (#52). CITATION.cff ships in the crate (#42, #44).