Performance roadmap: upstream cross-check, benchmark gate fixes, and next optimization experiments

[berkorbay]

Objective

Improve runtime and MIP gap closure on top of upstream latest, separating pure speedups from changes to the search path. Cross-checked upstream issues, PRs and relevant comments on 2026-09-25. This is a source/results review; no new solver benchmarks were run. Proposed gains remain hypotheses.

Reviewed lab snapshot: acc2726. Control: 6293630a84612d22e87a542d2f1fd2d1b6f07940.

Existing evidence

The three-seed hard-set comparison reports 2 vs 1 solved runs, 100 vs 97 feasible runs, unchanged mean gap of 55.7%, and worst overrun of 25.1 vs 282.4 seconds across 126 instance–seed pairs (42 instances). This supports better time-limit behavior, but does not establish a broad speedup. PDI needs correction below, and the run metadata records an active LLM server.

Upstream cross-check

Topic	Upstream evidence and current status	Implication
DSE preservation	PR #685, merged, already preserves DSE weights and notes scope for more. Issue #2230, closed, covers warm starts, recomputation, model changes and scaling.	Extend existing preservation; identify exactly which invalidation paths still cause unnecessary recomputation.
Strong branching and DSE	PR #688, closed unmerged; a maintainer comment says a different fix superseded it and reports sudden DSE-weight errors during strong branching.	Add freeze/unfreeze, strong-branching and full weight-recomputation comparisons. Historical evidence is a regression-test target, not proof the lab patch is wrong.
Repeated equation checks	PR #3035, merged, avoids rechecking unchanged equations; issue #2773, closed, discusses related dual-fixing overhead.	P1 optimizes invalidation cost after existing work. Preserve its recheck semantics.
Domain/probing changes	PR #3244, open, changes dual fixing, probing and domain-copy handling. A later comment reports neutrality on a larger set and loss of useful structure on neos-3046615-murg.	Keep scratch-buffer work independent of propagation semantics; inspect domain-copy behavior. Include neos-3046615-murg and neos-787933 in coverage. Do not treat the initial claimed gain as settled.
Clique structures	PR #3312, open, changes clique-table consistency through presolve. PR #2688, merged, fixes fixed-variable handling in clique merging.	Keep caches narrowly scoped, invalidate on mutation, preserve fixed/deleted-variable handling and recheck compatibility with #3312.
Implications	PR #3264, open, adds implication aggregation, explicitly excluding binary clique implications; toguru is affected.	Related moving code, not the same optimization as clique traversal. Re-profile after upstream changes.
Time limits	Issue #3314, open, is the existing s100 report; lab #2 has the later diagnosis. Issue #1930, closed, distinguishes normal timing from expensive development profiling.	Separate deadline handling from speed. Use bounded-frequency checks and measure instrumentation overhead.
Build tuning	PR #1104, closed unmerged, documents static-library/user-preference LTO concerns and platform CI failures.	Use supported, opt-in build experiments; do not assume universally enabling LTO is safe or novel.

Searches covered open and closed issues/PRs for steepest, DSE, propagation, clique, dual fixing, time_limit, LTO, PGO, profile guided, changedbounds, markChangedCol and find_common. No exact hits were found for changedbounds, markChangedCol, find_common or PGO/profile guided. That is not proof equivalent work does not exist.

P0: Reproducibility and acceptance gate

• Publish the exact benchmarked combined arm. At review, remote dev-tideseed and upstream latest both pointed to 6293630a84; bench/queue.txt contained only its header. Experimental branches exist, but this queue cannot reconstruct the documented combination. Record source SHA, ordered patches, compiler/version/flags, effective options, model checksum and binary hash.
• Fix analyze.py: crash counts are omitted from PASS, and required --identical failures are printed after the verdict without changing it. Make both enforceable; compare solved counts on the same paired set.
• Fix run.py resume validation: existing-file presence alone must not reuse results for changed binaries/options/time limits.
• Fix hard.py: zero PDI with unavailable bounds must not score as excellent performance. Record bound trajectories; integrate a defined normalized gap over the same horizon, assigning worst-case gap while bounds are unavailable. Report overrun separately. Bootstrap over instances, retaining their seeds together.
• Use a declared clean window for acceptance runs, separate diagnostic profiling from timing, and report correctness-check coverage. Missing reference objectives must not silently become evidence of correctness.

Prioritized solver experiments

1. Cheaper, more selective DSE preservation

Starting point: DSE patch.

• Split basis-restoration caching and cut-row weight carry into separate arms.
• Measure cache hits/misses, BTRANs avoided, cache time, bytes copied and retained memory.
• Compare current dense num_col + num_row entries against compact basic-variable/weight storage; test caching at actual basis-save points instead of every solve return, verifying coverage.
• Add matrix/scaling-generation validity checks and sampled comparisons against full recomputation. Exercise freeze/unfreeze, strong branching, row add/delete and scaling changes.
• Measure runtime and solution quality: reused floating-point weights can change pivoting/search. Node throughput alone is insufficient.

The lab's reported 24–27% recomputation shares justify priority, but cache overhead and end-to-end benefit need isolated measurement.

2. Reuse propagation scratch memory

The current source allocates a large changed-bounds array on each propagation call with pending work.

• Reuse a grow-on-demand buffer, including cut-pool nonzero capacity in sizing as current code does.
• Avoid deep-copying scratch storage with domains or unsafe sharing between simultaneous/reentrant uses.
• Measure allocations, page faults, peak RSS and runtime; require identical-search checks for a pure storage change.
• Profile first: the allocation is source-confirmed; its runtime share is not yet established.

3. Reduce repeated presolve invalidation walks (P1)

• Prototype lazy invalidation/generation stamps in markChangedCol(), preserving the recheck semantics from #3035. Simply returning when changedColFlag is already set is insufficient.
• Cover row/column modification, deletion, compaction and new rows; shadow-check against existing flags.
• Re-profile the reported 17.5% toguru hotspot after existing patches and upstream changes; historical profile shares are not necessarily additive.

4. Clique traversal locality and deadline handling

• For C2, test a mutation-versioned contiguous adjacency view for collectCliques(), preserving visitation order where it affects decisions. Measure rebuild and memory costs.
• Tune marking-versus-pairwise selection using measured adjacency/candidate costs; replace the fixed factor 16 only with held-out support.
• Retain collision, same-column, fixed/deleted-variable and mutation shadow tests from lab HighsHashTree::find_common can miss a common key when a leaf holds several entries with equal hashes #1/s100 time_limit overrun (upstream #3314): root cause is pairwise clique partition queries #2.
• Add bounded-frequency deadline checks to long pre-node work with a safe stop path, as a separately measured robustness change.
• Check #3312 compatibility before a broad clique-table redesign.

5. CPU tuning, LTO and PGO as separate build arms

• Compare baseline, CPU-specific tuning, supported LTO, then PGO on identical source.
• Train PGO on disjoint model families and evaluate held-out instances plus production workloads.
• Preserve floating-point semantics initially; report code size and memory alongside runtime.
• Verify actual compiler flags instead of inferring them from build or wheel defaults.

Experiment order and acceptance

1. Complete P0.
2. Screen upstream, combined-without-DSE, DSE-cache-only, DSE-row-carry-only and propagation-buffer reuse in the same session, isolating each treatment's baseline.
3. Follow with P1, clique-locality and build experiments according to fresh profiles.
4. Test the winning combination on held-out MIPLIB and representative production instances, including short solves and long gap-limited runs.
5. Retain the documented speed gate: shifted geometric-mean ratio <= 0.97, paired-bootstrap CI upper < 1, solved count no lower, zero detected wrong answers, no crashes, and identical search where claimed. Define a separate acceptance rule for deadline/quality improvements so they are not mislabeled universal speedups.

Keep findings in this lab. This issue does not request an upstream post or PR.

Prepared with Codex from repository source, recorded results and upstream discussions.

[berkorbay]

Thanks, this was useful. It caught real problems, and two of them bit us the same afternoon. Status against the review, as of 2026-09-25 15:35 CEST. Lab commits are on main; fork branches are on Tideseed/HiGHS.

P0

• Reproducible combined arm.
  • bench/queue.txt now lists the real ordered branches. bench/COMPOSITION.md maps each arm to its fork ref and source SHA.
  • The fork's dev-tideseed now points at the benchmarked combination, 9e9a3f98f2 = latest 6293630a84 plus these branches:
    • clique-partition-marking 39367bfe61
    • symmetry-dense-hash 51ebf64d2f
    • free-wins e1983642bf
    • dse-carry-weights 8dc4f6a81e
    • presolve-changed-col 5816d69698
  • dev-tideseed-nodse is the same combination without the DSE branch. The earlier combination is kept as tag dev-tideseed-v1.
  • Every run set's RESOURCES-*.json records per arm: source SHA, whether the tree was dirty, compiler version, effective CXX flags, CMake build type and LTO/shared settings. Every result records binary_sha (executable plus libhighs) and model_sha.
• analyze.py.
  • Crashes fail the gate. rc 1 (the time-limit warning) is not a crash.
  • With --identical, any difference fails the verdict, and the failure is listed in the verdict line.
  • Solved counts are compared on the paired set only.
  • Reference coverage is printed: runs without a solu.txt objective are stated as unverifiable, not counted as correct.
• run.py resume.
  • A result is reused only if binary hash, options, time limit and model hash all match. Otherwise it is renamed .stale.json and rerun.
  • The build hash is also checked before every job, and the run set aborts if it changed.
  • This was not hypothetical: a sweep this afternoon overlapped a rebuild of its build directory. 26/42 runs per arm crashed; the run is marked invalid (vault/60-incidents/) and is being rerun.
• hard.py.
  • HiGHS's P-D integral is replaced by our own PDGI. Bound trajectories are parsed from the progress log (trajectory in each result, backfilled for today's runs with bench/reparse.py). The normalised gap is integrated over the fixed horizon, with gap = 1 while either bound is missing or the signs differ.
  • Overrun is reported separately.
  • The bootstrap resamples instances with their seeds kept together.
  • Re-scored 3-arm hard set (42 instances × 3 seeds, 60 s): the old metric said dev-tideseed was 1.7 % worse than dev. PDGI says ΔPDGI −0.0043, CI [−0.0159, +0.0034], i.e. no measurable difference. stable vs dev: +0.049, CI [+0.008, +0.103].
• Clean acceptance window. Tonight 00:15–06:30, both local LLM servers are stopped (Berk's OK) and the jobs that would call them are paused. Scope: 240 instances × stable / dev / dev-tideseed / dev-tideseed-nodse, 300 s, seed 0. Profiling no longer runs concurrently with timing runs; today it did on disjoint cores, which still shares memory bandwidth.

Solver items

1. DSE. Split into cache-only and carry-only arms with counters (hits, misses, BTRANs avoided, bytes copied): tomorrow. Evidence so far:
   • seymour1 is 14–28 % faster on all 3 seeds, and node counts without DSE equal dev's. So the gain is from DSE.
   • neos-2978193-inde is +43 % slower (3/3 seeds), with equal throughput but larger trees: a search-path effect, not overhead.
   • The #688 history (sudden weight errors in strong branching) goes on the test list.
2. Propagation scratch buffer (S1). Not started. Profile first, then an identical-search arm.
3. P1.
   • Done as an exact counter instead of generation stamps. It counts rows with singleEquationChecked set, skips the column walk when none is set, and stops it at zero. The flags end up identical, so the #3035 semantics are preserved.
   • toguru presolve 12.5 s → 6.2 s with the same reductions.
   • Identical search vs dev on the small set: checking now.
4. Clique.
   • The review's "held-out support for the 16× factor" point was right, and it led to a real bug. Raising the factor to 64 changed neos-1445765's search path. The cause: haveCommonClique does not count a query for same-column literals, but the marking path counted all N, and the query count feeds effort limits. Fixed (39367bfe61). neos-1445765 is now identical to dev.
   • The shadow check (every marking result compared with pairwise queries) is kept in bench/patches/.
   • The factor 64 still needs held-out timing, as you say.
   • A deadline in clique merging (chromaticindex: 85–110 s for a 60 s limit) is filed as candidate T2. #3312 compatibility is checked first.
5. Build arms.
   • Measured on identical source, small set, 2 seeds: -mcpu=native 1.004 [0.992, 1.018]; PGO 0.970 [0.949, 0.989]; identical search 56/56 for both.
   • LTO is already on for the default shared build. PGO trained on non-MIPLIB families (PGLib-UC, ML4CO).
   • Kept separate from the code comparison.

Also measured today

Small set (33 instances × 3 seeds, 120 s):

• dev-tideseed v1 vs dev: 0.965 [0.913, 1.020].
• v2 vs v1: 0.971 [0.938, 0.996], but identical search 27/28. The one difference was the query-count bug above, since fixed.

These are screens, not acceptance numbers. Acceptance waits for tonight's clean run, with the gate as you restated it plus a separate rule for deadline and quality changes.

No upstream posts or new issues (Berk).