Separate the MINLP Rust–Python boundary: retire the duplicated B&B loops and make the native spatial path load-bearing

[jkitchin]

Companion to #1230, which does the same job for LP/QP. Same contract, different path — and a much larger one, so the ordering below matters more than the total.

The line

docs/dev/lp-qp-boundary.md §0 (on claude/bold-lovelace-9f1wzw, not yet merged) states it as "Python turns a Model into a problem; Rust turns a problem into a certified result," with the producer staying in Python.

That wording is too blunt for MINLP, and AMP is what shows it (see below). _relax/term_classifier.py moved an analyze-once DAG walk into Rust and was right to — a 53k-node body is slow even once per solve. The rule that actually holds:

The certificate must live in Rust and exist exactly once. Producer work may be accelerated in Rust wherever it pays. What is forbidden is a twin: the same computation implemented on both sides with a silent fallback between them.

For MINLP the crossing should also be once per solve, not once per node. Language is the second-order question; duplication with a silent fallback is the defect.

What is wrong

M1 — every MINLP algorithm exists twice, so eight solve loops are live

algorithm	Python	Rust
spatial (nonconvex)	inlined in solve_model, solver.py:12610	bnb/spatial_tree.rs:324 solve_spatial_tree
convex MINLP	_solve_nlp_bb, solver.py:17082	bnb/convex_kernel.rs:1200 solve_tree
MILP	_solve_milp_bb, solver.py:23091	bnb/milp_driver.rs:1166 solve_milp
MIQP	_solve_miqp_bb, solver.py:23811	—
AMP (adaptive multivariate partitioning)	solvers/amp.py:2865	— (Rust helper only; see below)

This is a half-finished port kept as mutual fallback, not a design. solve_model is ~9,000 lines (solver.py:7377–:16438) with the spatial node loop inlined into it.

M2 — the Python loops have drifted copies of each other

Measured by difflib.SequenceMatcher over the extracted bodies:

helper	sites	lines	similarity
_debug_validate_candidate	:12551, :17045	27 / 27	1.000 (verbatim)
_record_improver	:12061, :17036	6 / 6	1.000 (verbatim)
_improver_allowed	:12047, :17023	13 / 12	0.640
_maybe_inject_snapped	:22997, :23655	58 / 61	0.319

The two verbatim pairs are cheap to fix. The two drifted pairs are the real hazard: the same named helper now behaves differently depending on which loop you are in, and nothing says so.

M3 — the per-node relaxation layer is in Python, and its Rust twin is not load-bearing

_relax/ is 74,642 lines. Classified by how often the code actually runs:

bucket	files	lines	belongs
per-node hot path	24	27,935	Rust
analyze-once producer (incl. convexity/, symbolic/, presolve/)	22 + 3 dirs	33,567	stays Python (may be accelerated; see the line above)
no in-package consumer	6	2,199	delete
optional/research with consumers	7	3,984	out of scope
unclassified remainder	—	6,957	needs triage

Most of the hot path already has a Rust counterpart:

Python	LOC	Rust	LOC
mccormick_lp.py	3,102	bnb/spatial_kernel.rs	811
obbt.py	2,620	bnb/obbt_sweep.rs	197
cutting_planes.py	1,201	lp/gomory.rs	658
incremental_mccormick.py	1,178	bnb/mccormick_patch.rs	1,585
rlt_cuts.py	229	lp/aggregation.rs	484
cover_cuts.py	156	lp/cover.rs	350
cmir_cuts.py	151	lp/mir.rs	609

The blocker is producer coverage, not missing Rust. The native spatial kernel is default-ON (#764, graduated in #892) but its own re-graduation panel records engaged 4/66 (solver.py:875 — dispatch, nvs13, st_e13, tanksize). The producer declines ~94% of the corpus, so the Python loop is still the real engine on almost everything and neither path can retire. Writing more Rust does not change this number.

M4 — dead weight that must not be ported

Verified to have no importer anywhere in the package outside their own file: differentiable_solve.py (329), icnn_trainer.py (501), chebyshev_model.py (435), taylor_model.py (411), ellipsoidal_arith.py (393), embedding.py (130) — 2,199 lines. Separately there are 158 distinct DISCOPT_* flags (64 read in solver.py alone), 17 of them default-"0", several of which never graduated.

M5 — AMP is the worked example of the twin pattern (and is not a consolidation target)

AMP (Adaptive Multivariate Partitioning, Nagarajan et al. CP 2016 / JOGO 2018) was contributed by @bernalde in #44 and #86. It is a distinct global algorithm — MILP relaxation for LB, fixed-interval NLP for UB, adaptive partition refinement — not a variant of spatial B&B. It is opt-in (solver="amp", solver.py:8691), never on the default path, and carries 3,523 lines of Python, 799 lines of Rust, 8,837 lines of tests and its own CI workflow (.github/workflows/amp-integration.yml).

It is listed here for three reasons, all informational:

1. It is the eighth loop (amp.py:2865) and was missing from the original M1 table.
2. It shares the M3 hot path. amp.py imports _relax/milp_relaxation, _relax/nonlinear_bound_tightening and _relax/model_utils, so M3 work touches AMP whether or not it intends to. Anyone changing those modules needs the AMP CI lane green.
3. It states the inverted boundary explicitly, and demonstrates the twin defect. amp.rs:1-4: "keep the high-level AMP algorithm in Python while moving repeated expression-tree walks into Rust." Its one exported routine reaches Python through _relax/term_classifier.py:662, which tries the Rust classifier and falls back to _classify_nonlinear_terms_python — declining when general_nl_count != 0, when the model has an expandable square, and, via two bare except Exception: return None, on any Rust failure at all. The code's own comment says "the Rust term classifier has blind spots." Same shape as the spatial kernel at 4/66.

Two consequences worth acting on independently of AMP's future:

• amp.rs is misnamed. classify_nonlinear_terms is general term-classification infrastructure consumed through term_classifier.py across the codebase, not AMP-specific. Nobody consolidating _relax/ would think to look in a file called amp.rs.
• The two silent except Exception: return None fallbacks should report. A Rust classifier failure currently degrades to Python with no signal — CLAUDE.md §7 in production code rather than in an instrument.

Explicitly out of scope for this issue: whether AMP is kept, retired, or restructured. It is a contributed, opt-in, separately-CI'd subsystem, and that decision belongs with @bernalde rather than being swept into a de-duplication pass. Consolidating our own half-finished port is a different kind of change from restructuring a collaborator's contributed algorithm.

Work, in order

The ordering is the point. Doing 3 before 1 and 2 grows the tree instead of shrinking it.

1. Delete before porting. Remove the M4 modules and the default-off flags whose paths never graduated. Cheapest large reduction, needs no Rust, and it stops the port from carrying dead code across the boundary. Bound-neutral by construction — verify with an unchanged smoke suite.

2. Raise producer coverage until the decline rate is near zero. Instrument build_spatial_kernel_spec to report why it declines, per instance, over the in-repo corpus and the MINLPLib snapshot; then close the top decline reasons. This is the gating measurement for everything after it. Definition of progress: engaged N/66 where N is tracked and rising. Until this lands, the Rust kernel is a second implementation rather than a replacement.

3. Retire each Python twin the moment its Rust counterpart is default-ON and its producer is near-total. Make the deletion a deliverable of the same PR, not a follow-up — deferred retirement is how eight loops accumulated. Bound-neutral: identical node_count and certified objective on a certifying panel; any drift means the change is wrong.

4. Fold M2's duplicated helpers into one definition while the loops still exist. Independent of everything else and safe now; the two verbatim pairs are trivial, and the two drifted pairs need a decision on which behavior is correct before merging them.

5. Move the remaining hot-path relaxation code into Rust, per-family, each behind the CLAUDE.md §5 regime appropriate to it (bound-neutral for a straight port, bound-changing for anything that alters an envelope or a cut).

6. Make the remaining producer twins loud, not silent. Wherever a Rust producer path falls back to a Python one (term_classifier.py:662 is the known case), the fallback must be counted and surfaced, so "the Rust path is in use" is a measured fact rather than an assumption. This is the M5 lesson generalized, and it is a precondition for retiring any producer twin.

Explicitly out of scope

The 33,567-line producer bucket stays in Python as the default. convexity/ (11,412), symbolic/ (3,521), problem_classifier.py, term_classifier.py, factorable_reform.py, gdp_reformulate.py and the rest are symbolic pattern-matching over a DAG that runs once per solve. That is the modeling-language producer this architecture is meant to keep in Python. Accelerating a specific hot walk in Rust is allowed where measured to pay (that is what AMP's classifier did); wholesale porting the bucket is the mistake this issue exists to avoid.

AMP's future — see M5.

Done when

• One solve loop per algorithm, in Rust, with the Python twin deleted rather than flagged off (AMP excepted, per M5).
• The spatial producer's decline rate is tracked and near zero on the in-repo corpus.
• No remaining Rust/Python twin falls back silently — every fallback is counted and surfaced.
• _relax/ contains no module without an in-package consumer.
• Every retirement is evidenced bound-neutral (node_count and objective exactly unchanged) or, where it isn't, carries its §5 panel.

Expect this to land as many PRs. Use Contributes to rather than a closing keyword until the loops are actually gone.

Context: #764 (kernel), #892 (default-ON), #902 (the incumbent-quality regression that ungraduated it once), #789 (feature parity), #1230 (LP/QP companion), #44 / #86 (AMP).

[bernalde]

John, I support proceeding with the consolidation in this issue. Please go ahead with the default-engine work; I will take care of comparing AMP with the current default solver so we can make a separate, evidence-based decision about AMP.

I am open to retiring AMP if it does not provide a repeatable benefit that justifies its maintenance cost. For now, I would keep it as an opt-in path and preserve compatibility when changing the shared relaxation infrastructure. I would defer an AMP rewrite until we have the comparison. Extracting AMP into a separate package is off the table: the eventual choice is to retain it within DiscOpt, with whatever restructuring the evidence warrants, or deprecate and retire it.

The comparison will use a pinned current revision and focus on nonconvex families that actually exercise partitioning, rather than counting convex fast-path successes as evidence for AMP. I will record certified solves, independently checked primal feasibility and objective values, bounds against available reference optima, time to close the gap, and memory. Solver dispatch, MILP/NLP backend choices, tolerances, and budgets will be explicit, with interleaved repetitions for timing claims. We can then decide whether AMP has a useful class of wins, needs a more targeted follow-up, or should be retired.

The shared cleanup can proceed independently: renaming the general classifier in amp.rs, reporting classifier fallback reasons, and consolidating shared relaxation and certification machinery all make sense. The classifier's Python fallback currently covers real unsupported cases, so removing it should follow demonstrated coverage parity or explicit unsupported-model handling.

For AMP specifically, I would judge the boundary by ownership of relaxation validity, trusted bounds, incumbent validation, and certified termination. Moving the outer loop or gap arithmetic to Rust alone would not settle those responsibilities; the performance case for moving coarse MILP/NLP orchestration should also be measured.

If the comparison supports retirement, I would preserve the reusable relaxations, regression cases, and benchmark fixtures while deprecating the AMP entry point. No retirement or Rust port is being decided in this comment.

[bernalde]

Following up on the comparison promised above: keep AMP as an opt-in method inside DiscOpt for now, scoped to correctness/compatibility maintenance and improvements to shared infrastructure. Defer a full Rust AMP port. AMP will not be extracted into a separate package.

The comparison used source 66d341df0ab8da383f97207f9f3f4145d9789b4b, a 30-second budget per instance, a requested relative gap of 1e-4, and the same cross-solver feasibility, reference-objective and certificate checks. The panel contains 48 feasible cases (translated NLP/MINLP tests, Alpine-style fixtures and MINLPLib cases) plus three infeasibility controls. Gurobi was version 13.0.2; the DiscOpt configurations used POUNCE 0.11.0 for NLP subproblems.

Configuration	Certified optima under shared checks	Reference-quality feasible points	Penalized shifted geometric mean time (s)
DiscOpt default	45/48	48/48	1.517
AMP, in-house MILP	27/48	42/48	3.939
AMP, Gurobi MILP	27/48	45/48	3.824
Direct Gurobi, outside DiscOpt	45/48	47/48	0.251

All four configurations correctly classified the three infeasibility controls. Certification requires an independently checked feasible point, reference-quality objective, compatible global bound and closed gap; native solver status alone is insufficient.

The time column covers all 51 primary-screen cases, with a 1-second shift: exp(mean(log(t_i + 1))) - 1. Uncertified results and errors use max(measured solve time, 30 seconds); successful cases use measured solve-call wall time. Imports, validation and direct Gurobi's one-time export/audit are excluded. These are screening measurements, not a fully interleaved four-way timing experiment; repeats and changed-setting diagnostics are excluded from this table.

Direct Gurobi reported 46 OPTIMAL results and two SUBOPTIMAL results. One OPTIMAL result (alpine_multi4n) narrowly misses the shared gap threshold; a separate tighter-gap diagnostic passes, but is not substituted into the primary table. Default and direct Gurobi also certify different sets: Gurobi adds tanksize and nvs05, while default adds nlp_001_010 and nlp_mi_001_010. The exported models can be solved and independently validated without installing or importing DiscOpt.

Why retain AMP, but limit investment? Neither AMP configuration adds certified coverage beyond default, and replacing its MILP subsolver with Gurobi certifies exactly the same 27 cases. That does not justify a full Rust port on performance grounds. However, AMP has repeatable instance-level wins even with the in-house MILP solver: on nvs09, three interleaved, load-gated repeats gave 5.049 ± 0.074 s for default versus 1.318 ± 0.021 s for AMP (mean ± sample standard deviation; all certified). Those benefits deserve preservation. This focused panel does not establish a broad problem-family advantage.

The priorities I support are:

1. John proceeds with the default-engine consolidation in this issue. Share classifiers, relaxations and certificate handling where appropriate, preserving AMP compatibility when changing shared modules. Retaining AMP does not require retaining duplicated default B&B loops.
2. Extend the explicit, optional solver="gurobi" backend to general NLP/MINLP. The tested interface only exposes linear/quadratic classes. Validate expression/domain export and primal/dual status mapping against the standalone Gurobi baseline, and retain external runs as an independent comparison.
3. Use the demonstrated AMP wins as regression and acceptance targets, and make maintenance ownership explicit. AMP-specific ownership is still unresolved; this does not assign that responsibility to John. Larger AMP investments would need evidence of a broader benefit.

Retirement criterion: if the consolidated default absorbs AMP's useful advantages, or nobody is willing to maintain AMP, deprecate its entry point and eventually retire the implementation while preserving reusable relaxations, regression cases and benchmark fixtures. No separate AMP package.

This records the AMP direction; #1231 remains open for the consolidation work described in the issue.

[jkitchin]

Thanks for this input! I am working through a few decisions, it actually looks like the minlp side of discopt is quite a bit stronger than the milp side(whew, the milp has been dogging me lately, and I am leaning towards letting highs take that over.).

I am not actively looking to retire AMP by any means, and this issue is somewhat a thinking out loud WIP.