Possible race: RINS worker incumbent size can mismatch leaf_problem.num_cols in branch_and_bound.cpp

[ramakrishnap-nv]

Surfaced by draft PR #1905 (compiling against a different OpenMP runtime, which shifts B&B task-scheduling timing). CI hit a native assertion abort:

```
branch_and_bound.cpp:3066: Assertion `worker->current_incumbent.size() == worker->leaf_problem.num_cols' failed.
Fatal Python error: Aborted
```
in `tests/linear_programming/test_incumbent_callbacks.py::test_incumbent_get_set_callback[/mip/neos5-free-bound.mps]`. A separate CI run on the same branch also saw `test_mip_incumbent_stream` time out, which may be the same underlying issue.

Where

```cpp
if (use_rins) {
mutex_upper_.lock();
worker->current_incumbent = incumbent_.x;
mutex_upper_.unlock();
assert(worker->current_incumbent.size() == worker->leaf_problem.num_cols);
}
```
(cpp/src/branch_and_bound/branch_and_bound.cpp, around line 3062-3066)

`incumbent_.x` is copied under `mutex_upper_`, so the copy itself isn't torn — but nothing guarantees `incumbent_.x`'s dimensionality matches this worker's `leaf_problem.num_cols` at the moment of the check. Since #1543 already documents this same test as timing-sensitive (`test_incumbent_get_set_callback[swath1.mps]` failing with TimeLimit on oldest-deps), this looks like a pre-existing race whose trigger probability is just sensitive to B&B/OpenMP scheduling timing, not something introduced by #1905 itself — worth confirming whether it reproduces on main with enough repetitions, and whether `leaf_problem` can legitimately have a different column count than the global incumbent (presolve column elimination in submip construction?).

Related: #1543, #1774 (a previous concurrent-access race in `clique_table_` with the same "scheduling-timing-dependent" shape).

[ramakrishnap-nv]

Second occurrence, same exact assertion, on a retry of the identical commit (458614d) — this time in INCUMBENT_CALLBACK_TEST rather than the Python test_incumbent_callbacks.py test. First attempt on this commit also failed here (plus a separate gRPC timeout); the immediate retry of the same commit passed everywhere except this one leg. Consistent with a real, intermittent pre-existing race rather than a one-off — not something #1905 introduces, since the assertion fires in plain host code unrelated to the OpenMP runtime change, just triggered by timing that differs slightly run to run.

[ramakrishnap-nv]

Third occurrence, different test this time (test_incumbent_get_callback[/mip/neos5-free-bound.mps], Python wheel test), same exact assertion. Further confirms this is a real pre-existing race, not tied to any specific test or to #1905's libgomp change.

[ramakrishnap-nv]

Fourth and fifth occurrences (conda-python-tests, two legs). One interesting new detail: this one fired at branch_and_bound.cpp:3131, not :3066 like the others — same assertion (current_incumbent.size() == leaf_problem.num_cols), different call site. Worth checking if there's more than one place doing this same unguarded incumbent-vs-leaf_problem size check.

[ramakrishnap-nv]

Root cause found (high confidence, static analysis + git history — not yet empirically confirmed with a forced repro)

This is a genuine race, not a legitimate size difference. create_submip_worker/create_diving_worker (cpp/src/mip_heuristics/root_heuristics.hpp:75-132) always construct leaf_problem as a straight copy of the current lp (branch_and_bound/worker.hpp:115-143, leaf_problem(original_lp)) — no column elimination happens for RINS/diving workers. RINS "fixing" (apply_rins_fixings, branch_and_bound.cpp:2612-2635) only narrows variable bounds, never removes a column, and indexes worker->current_incumbent[j] directly against leaf_problem's column space — the code assumes 1:1 column-index alignment. No column_map/var_map remapping exists on this path (the only such remapping in the codebase is unrelated device-side presolve code). So leaf_problem.num_cols should always equal the incumbent's dimensionality — when it doesn't, something is actually wrong, not "expected."

The actual bug: two lock-discipline gaps around original_lp_ growth

original_lp_.num_cols legitimately grows during root cut passes — add_cuts adds slack columns for new cuts under mutex_original_lp_ (branch_and_bound.cpp:3404-3418). Two separate places try to keep incumbent_.x in sync with that growth, and both have a gap:

1. TOCTOU in add_feasible_solution (branch_and_bound.cpp:940-980):

mutex_original_lp_.lock();
// ... check leaf_solution.size() vs original_lp_.num_cols, uncrush/crush into `sol` if mismatched ...
mutex_original_lp_.unlock();
...
mutex_upper_.lock();
incumbent_.set_incumbent_solution(leaf_objective, sol.empty() ? leaf_solution : sol);   // writes `sol`, computed under a lock already released
mutex_upper_.unlock();

The size-check-and-reproject happens under mutex_original_lp_ (950-957), but the actual write into incumbent_.x happens later, under a different lock (mutex_upper_, 964-966). Nothing prevents original_lp_ from growing again (via a concurrent add_cuts) in the gap between the two lock sections — so sol can be stale (crushed against an already-outdated column count) by the time it's written.

2. Missing lock coverage in the end-of-cut-pass resync (branch_and_bound.cpp:3926-3933):

mutex_upper_.lock();
if (incumbent_.has_incumbent && incumbent_.x.size() != original_lp_.num_cols) {
  uncrush_primal_solution(original_problem_, original_lp_, incumbent_.x, uncrushed_incumbent);
  crush_primal_solution(original_problem_, original_lp_, uncrushed_incumbent, new_slacks_, incumbent_.x);
}
mutex_upper_.unlock();

This reads and uses original_lp_ (the size check, and inside uncrush_primal_solution/crush_primal_solution) while holding only mutex_upper_ — not mutex_original_lp_, the lock that actually protects original_lp_ from concurrent modification by add_cuts. That's an unsynchronized read of a structure another thread can be actively resizing, independent of the timing/staleness question above — undefined behavior on its own.

Git history is consistent with this: the incumbent-resize-on-cut-growth mechanism (889a697e, "Root heuristics #1700") predates the RINS/diving asserts (3bb1bed3, "Diving on cut passes #1812") — the asserts were added on top of a codepath that already had these gaps, without closing them. This also explains why the crash has been observed at both assert sites (3066 RINS, 3131 guided diving, per this issue's history) — both are just readers hitting the same underlying racy incumbent_.x.

Why the obvious "just widen one lock" fix isn't enough

Widening the lock in add_feasible_solution alone doesn't fix bug #2 (the resync's missing mutex_original_lp_ coverage). A correct fix needs consistent locking discipline across both sites — every place that reads original_lp_ for the purpose of sizing/reprojecting the incumbent needs to hold mutex_original_lp_ for that read, not just whichever lock happens to be convenient at each call site.

Fix options on the table

1. Close both gaps: widen critical sections so the check→reproject→write sequence in add_feasible_solution is atomic w.r.t. original_lp_ growth, and add mutex_original_lp_ coverage to the resync's read of original_lp_. This is the real fix.
2. Defensive projection at the two assert sites (branch_and_bound.cpp:3062-3067, 3127-3132) using the existing uncrush_primal_solution/crush_primal_solution utilities instead of asserting on mismatch — cheap, no regression in the common (no-race) path, but on its own this only prevents the crash, not the underlying incumbent corruption (RINS could silently fix variables against a stale/wrong-generation incumbent with no visible symptom). Should be additive on top of (1), not a substitute for it.

Open questions before landing a fix

• Performance: widening mutex_original_lp_'s critical section is structurally not new work (same uncrush/crush calls, just held under a continuous lock instead of released-and-reacquired), so the expected impact is small, but this needs actual before/after benchmarking on the existing MIP suite, not just reasoning — cut-pass-heavy instances with frequent concurrent incumbent updates are the case to check.
• Reproducibility: this is a pure host-side CPU race (OpenMP task-scheduling timing around cut-pass/incumbent-update overlap), not GPU/VM-timing dependent like some other flaky tests in this repo — so unlike those, it should be possible to force it reliably with a test-only injected delay widening the race window between the two lock sections in add_feasible_solution, to (a) confirm this theory actually reproduces the assert on demand, and (b) confirm a fix actually closes it, before removing the injection and landing the real fix.

Neither of these has been empirically confirmed yet (no injected-delay stress test has been run) — this is a static-analysis-and-git-history finding, not yet a verified reproduction. Flagging that clearly so nobody reads this as "confirmed and fixed."

[ramakrishnap-nv]

Correction to finding #2 above (the "missing lock coverage" claim)

That claim was wrong — thanks to @ramakrishnap-nv for catching it. Re-verified by exhaustive grep of every write site:

• add_cuts (the function that grows original_lp_.num_cols) has exactly one call site in the file: branch_and_bound.cpp:3405, inside do_cut_pass, called synchronously from the single-threaded cut-pass loop (branch_and_bound.cpp:3907) — never inside an omp task.
• Every other write to original_lp_ (bound updates, remove_cuts, etc.) is likewise confined to that same sequential main-thread control flow.
• Background workers (omp tasks for fj_cpu/RINS/RENS/diving) only ever read original_lp_, always under mutex_original_lp_ — none of them write/resize it.

Since add_cuts/bound writes and the resync snippet (3926-3933) all execute on the same single thread in strict program order (do_cut_pass returns before the resync runs), no lock is needed for cross-thread protection against original_lp_ mutation at that specific point — program order alone suffices. This part of my original writeup was incorrect.

One nuance worth keeping in mind: this correctness currently depends on an implicit, unenforced invariant — "only the main thread ever calls add_cuts/writes original_lp_" — true today by inspection, not guaranteed by the type system. Worth a comment in the code if this resync logic is touched, so a future change that moves cut-adding into a background task doesn't silently reintroduce a real race here.

The other finding (the TOCTOU in add_feasible_solution, lines 940-980 — check under mutex_original_lp_ followed by a write under a separately-acquired mutex_upper_) is unaffected by this correction and still stands as the actual, valid race.