perf(minlp): diagnose the integer-heavy node-count tail (nvs02/nvs14/nvs13/tls2/fac2, 24-297x SCIP)

[jkitchin]

Summary

On the global50 panel discopt proves more instances than SCIP overall (47/50
vs 44/50, node ratio median 1.00x), but a handful of integer-heavy instances
cost 20–300x SCIP's nodes. This issue records the reproduction and the
diagnostic plan for that tail.

The working hypothesis going in was "discopt's missing MILP cuts leak into the
MINLP path." The reproduction below does not support that as a single
explanation — the five instances take three different code paths, and the two
worst ones already have a nearly-closed root bound.

Reproduction (deterministic, ~55 s total)

Node counts reproduce the panel exactly, so this needs no benchmark harness.

cd <worktree on main>
PYTHONPATH=$PWD/python python -u <<'EOF'
import os, time, logging
logging.basicConfig(level=logging.INFO, format="%(name)s %(levelname)s %(message)s")
import discopt, discopt._rust
from discopt.modeling.core import from_nl
root = os.path.abspath("python") + "/"
assert discopt.__file__.startswith(root), discopt.__file__          # CLAUDE.md §8
assert discopt._rust.__file__.startswith(root), discopt._rust.__file__
B = os.path.expanduser("~/Dropbox/projects/discopt-minlp-benchmark/minlplib/nl")
ran = 0
for inst in ["nvs02", "nvs14", "nvs13", "fac2", "tls2"]:
    logging.getLogger("probe").info("=== BEGIN %s ===", inst)
    m = from_nl(f"{B}/{inst}.nl"); t = time.perf_counter()
    r = m.solve(time_limit=60); ran += 1
    print(f"{inst:6s} nodes={r.node_count} root_bound={r.root_bound} "
          f"root_gap={r.root_gap} bound={r.bound} wall={time.perf_counter()-t:.2f}")
    print("   stats:", dict(sorted((getattr(r, "solver_stats", None) or {}).items())))
print("RUNS_EXECUTED", ran); assert ran == 5
EOF

The assert on discopt.__file__ is not optional. The first attempt at this
run silently imported discopt from an unrelated worktree (wt2122) because the
editable install points elsewhere; without the assertion it would have measured
the wrong tree.

Measured, on main @ 0587f527

inst	discopt nodes	SCIP nodes	ratio	root_gap	path taken
nvs02	297	1	297x	0.40 %	MILP driver (lp/driver_nodes=297)
nvs14	273	1	273x	0.59 %	MILP driver (lp/driver_nodes=273)
nvs13	637	27	24x	None	native spatial kernel (#764)
tls2	399	15	27x	47.1 %	convex-MINLP auto-route → fallback
fac2	39	1	39x	23.1 %	convex-MINLP auto-route → fallback

All five return optimal with the correct objective (oracle from
minlplib.solu), so this is a work problem, not a correctness problem.

Wall times are not reported: load moved 3.80 → 7.99 during the run
(CLAUDE.md §9). Node counts are deterministic and match the earlier panel
exactly, so they are the metric to use here.

Why "missing cuts" is not obviously the answer

A missing-cuts story predicts a weak root bound. On the two worst instances
the root bound is already within 0.4 % and 0.6 % of the optimum, and discopt
still spends 297 and 273 nodes closing it. Cuts that tighten a bound which is
already 99.6 % closed are not the obvious lever.

tls2 (47 % root gap) and fac2 (23 %) are the two where a bound-strength story is
plausible — and they are on a different path from the nvs pair.

Three separate leads, each with a kill criterion

Lead 1 — nvs02 / nvs14: 297 nodes to close 0.4 %

These run on the MILP driver (lp/driver_nodes equals node_count
exactly). 5553 and 5298 LP iterations respectively.

Candidate causes: the termination gap test never fires despite the bound being
closed; integer bound propagation not rounding on the nonlinear integer columns;
branching repeatedly choosing a variable that does not tighten the bound.

Diagnose: dump per-node (depth, branch var, bound) and find where the bound
stops improving. If the bound reaches the optimum early and the tree keeps
expanding, it is a termination/propagation bug, not cuts.
Kill criterion: if the bound improves monotonically across most of the 297
nodes, the termination hypothesis is dead and bound strength is back in play.

Lead 2 — nvs13: the native spatial kernel, no stats at all

nvs13 takes the native spatial kernel (#764) path (log line: exited optimal: obj=-585.2 bound=-585.2 nodes=637), reports root_bound=None,
root_gap=None, and an empty solver_stats.

Diagnose: this path is currently unmeasurable from Python. Surfacing
root_bound/root_gap and node counters from the spatial kernel is a
prerequisite for diagnosing it at all.
Kill criterion: none yet — this is instrumentation work before it is a
performance question.

Lead 3 — tls2 / fac2: the convex-MINLP auto-route gives up, repeatedly

Both spend budget in the convex-MINLP auto-route, fail to certify, and hand back
to the fallback — tls2 does this five times in one solve (0.40 s, 0.13 s,
0.44 s, 0.73 s, 0.74 s), each time "falling back to the default path".

Diagnose: measure how much of the 38.8 s (tls2) and 13.8 s (fac2) is spent in
routes that certify nothing, and whether the route's decision point (#1143,
"stopped at 6.0s of 60.0s") is mis-tuned for instances this small.
Kill criterion: if the abandoned routes account for <10 % of wall, this is
noise and the nodes are the real story.

Correctness signal seen while reproducing (may deserve its own issue)

Both tls2 and fac2 emit:

discopt.solver WARNING #1059 route objective 5.3 appears to beat the fallback's
CERTIFIED 5.3; keeping the certified result. This should be impossible and
indicates a bound or feasibility inconsistency worth investigating.

The guard does the right thing (keeps the certified result), and the final
answers are correct. But the warning says the condition should be impossible,
and it fires on 2 of 5 instances here. Per CLAUDE.md §1 that outranks any of the
performance work above.

A metadata trap for whoever picks this up

problem_sizes.csv reports integer=0, discrete=0 for nvs02, nvs14 and nvs13.
That is misleading — it appears to count only linear integer variables. The
.nl headers show the opposite:

inst	vars	cons	.nl discrete line (nbv niv nlvbi nlvci nlvoi)	reading
nvs02	8	3	0 0 3 2 0	5 integers, all in nonlinear terms
nvs14	8	3	0 0 3 2 0	5 integers, all in nonlinear terms
nvs13	5	5	0 0 5 0 0	all 5 vars integer and nonlinear
tls2	37	24	31 0 0 2 0	31 linear binaries + 2 nonlinear
fac2	66	33	12 0 0 0 0	12 linear binaries

So the nvs family is integers inside nonlinear terms, not a linear MILP core.
Any framing of these as "small MILPs with a nonlinear wrapper" is wrong, and a
fix aimed at linear cut generation would not touch them.

Related

• perf(modeling): model construction is ~2.1x slower and ~1.9x heavier than Pyomo — tracking issue #1215 — model construction cost.
• solver.py:11199-11204 already names "the nvs* gap" and describes routing
  nonlinear-term integers to the LP-form McCormick relaxation with spatial
  integer branching; worth confirming that path is actually taken here.
• CLAUDE.md §2: the fix must target the class, not these five names. They are
  gate probes.