Hybrid restart: relaxed numerical search, exact completion

Archived experiment record. Findings and measurements are historical; see current research status. Original bytes and commands are preserved at Git tag research-before-cleanup-2026-09-21.

This is a new experimental search path. The existing 95.0668%, 45-piece exact partial certificate remains the benchmark. It is not modified by these runs.

The handoff target is configurable; the default experiment compares 80% and 90% with identical per-phase budgets and random seeds. Neither percentage is known to guarantee a tractable remainder. If a budget ends early, the report records the actual numerical and exact coverage separately.

The two phases

1. Numerical construction. Propose repeated box/octant cuts and one of the 24 proper axis rotations. Optimize translations against a smooth sampled occupancy loss, then snap translations and axis-cut offsets to a rational grid. Solve an LP relaxation over competing proposed placements and use its fractional weights to shortlist whole placements for geometric subtraction.
2. Exact handoff and completion. Replay the recorded rational cuts and motions against the exact algebraic roots. Independently check the resulting partial certificate. Search the entire remaining source and target, using exact candidates, complementary cuts, new motions, and exact collision and volume constraints. Independently verify any proposed complete result.

For proposed placements j, the numerical LP uses variables 0 <= x[j] <= 1, maximizes a volume/quality utility, constrains sampled occupancy at both endpoints to at most one, and constrains fractional piece usage to the remaining numerical allowance. This is an actual LP relaxation of the sampled selection problem. It is not an exact geometric bound, a certificate, or a global continuous parameterization of every possible dissection. Rounding is used for ranking, not for declaring a set of pieces compatible.

The old whole-solid optimizer was a numerical beam search. Separate older lattice/common-core experiments contained LP/MILP selection. The new numerical phase explicitly connects continuous translation optimization and LP selection to exact replay and completion. Its exact combinatorial phase uses the existing exact-cover/volume-cover machinery rather than a floating MILP feasibility flag.

What changed in the search space

• Fresh starts by default. An optional verified certificate can seed a run; it is reopened before search, and none of its groups is mandatory.
• Structured cuts and motions. A small repeatable family of rational boxes, octants, axis rotations, and rational translations reduces independent interfaces. The exact phase can add other proper algebraic motions. This is deliberately restricted, and a failed search is not an impossibility result.
• Piece reserve. With a limit of 99 physical pieces, the default numerical allowance is 69, leaving 30 slots available at handoff. Exact reconstruction checks connected physical groups again; a numerical group is not trusted to remain connected. Exact completion's convex-row budget is conservative.
• Balanced pieces. Soft costs retain volume/shape balance and penalize dominance. Skinny exceptions remain permitted.
• Residual quality. Score component count, tiny component volumes, and volume-weighted component aspect/convex-fill proxies. These describe connected unions, not artificial bookkeeping cells. They do not measure all narrow necks or prove fabrication strength or assembly feasibility.
• Early handoff. Coverage beyond the target receives no additional volume reward. The first retained candidate meeting the threshold is handed over; this is not a proof that it is the best handoff candidate.
• Broader retries. After an exact failure, reopen whole earlier operations totaling at least 30% of the currently matched volume (larger on later retries), restoring material at both endpoints. Releasing by operation makes exact replay unambiguous. Retries may recut these regions freely.

Exactness and failure handling

Fresh numerical placements retain their original construction instructions. Handoff does not round every recovered mesh face: exact root faces already live in Q(s), with s^6 - 190*s^3 - 3475 = 0, 5 < s < 6; all additional axis cuts and translations are rational. The exact builder intersects both residuals and records complete endpoint cut trees.

Numerical geometry can still differ from exact replay. No tolerance-based mesh is promoted to a certificate. A replay timeout retains only the completed exact prefix; its actual coverage and an all_events_replayed flag are reported. Even a prefix below the requested target may receive a bounded completion probe. All saved result certificates pass the independent checker. If completion fails, the output is explicitly partial, and the earlier best benchmark remains unchanged. Zero floating residual is never used as the completion condition.

Each output records phase budgets, random seed, numerical quality, LP outcomes, exact replay events, actual verified handoff coverage, and completion failures. Budgets are cooperative: root construction, import, and independent final verification are additional work. New output paths are required to avoid overwriting previous results.

Run and inspect

uv run --with scipy python -m experiments.hybrid_search \
  --handoff .8 .9 --rounds 2 \
  --numerical-seconds 60 --replay-seconds 60 --exact-seconds 60 \
  --max-pieces 99 --reserve 30 \
  --output .research-cache/hybrid-comparison.json

Use --handoff .8 or --handoff .9 to test one setting. --warm-start accepts a verified cut-tree or convex-partition certificate; materializing a large partition may be expensive, so the preserved incumbent is optional. The first run for each handoff otherwise starts from empty roots.

Outputs alongside the main certificate include a .report.json, numerical .geometry.json files, exact .recipes.json instructions, and each verified .partial.json certificate with its verification report. Numerical meshes and LP reports are labeled as proposals rather than certificates.

For larger Rust-backed runs, computational limits are configurable separately from the physical-piece budget:

SCISSORS_GEOMETRY_BACKEND=rust uv run --extra native python -m experiments.hybrid_search \
  --handoff .8 --rounds 1 \
  --numerical-seconds 420 --replay-seconds 360 --exact-seconds 120 \
  --cell-limit 2000 --replay-leaves 6000 \
  --exact-candidates 1024 --exact-atoms 6000 --residual-weight .3 \
  --max-pieces 99 --reserve 30 --seed 31 \
  --output .research-cache/hybrid-80-larger.json

These phase budgets total 15 minutes; independent verification and setup are additional, and a successful handoff can end the numerical phase earlier. --cell-limit caps numerical residual cells per endpoint; --replay-leaves caps all exact partition leaves per endpoint, including matched leaves. --exact-candidates and --exact-atoms bound the completion library and its source-subtraction bookkeeping. --residual-weight scales the existing soft component/shape/island penalty; it is not a hard handoff quality requirement. The original defaults remain 500, 2000, 192, 2000, and 0.08, respectively.

The numerical phase retries up to five consecutive empty/rejected proposal batches with fresh randomized templates and motions. It records the stopping reason, residual-cell counts, and rejection counts. A .numerical.json report is saved before exact replay so those diagnostics are available during long verification. The search still hands over the first retained candidate reaching the requested coverage, so inspect its residual metrics before calling it a promising completion problem.

The implementation is in experiments/hybrid_numerical.py and experiments/hybrid_search.py. Existing search entry points remain available for comparisons. Tests cover fractional LP solutions, endpoint coupling, exact replay/release, timeouts, piece reserves, residual quality, warm starts, and a complete box example through the full pipeline.

Performance and implementation language

SciPy's optimization backends already execute compiled code. The new numerical reports time smooth translation, candidate intersections, LP solves, residual subtraction, and quality ranking separately. Measure these before choosing a native extension. Repeated clipping/overlap and algebraic number arithmetic are candidate acceleration targets; a full rewrite of orchestration is not required. Keep the existing Python exact checker as an independent acceptance reference if the search geometry is later ported.

An eight-second instrumented numerical probe spent about 0.021 seconds in LP relaxation, 3.035 seconds in residual subtraction, and 3.017 seconds in Poly.make. These are inclusive timings that overlap; do not add them. Smooth translation took about 0.156 seconds. This supports targeting geometry construction/clipping and avoiding repeated hulls before rewriting the controller. It does not measure a Rust/C++ speedup, and it does not profile the exact arithmetic phase.

First TI smoke pilot

The saved pilot report used one fresh start per setting, seed 31, 45 seconds of numerical search, 30 seconds of exact replay, and 20 seconds of exact completion per setting. Root setup and independent verification were additional. The pilot ran before removing redundant verification/import of the unchanged handoff, so current runs avoid that extra overhead. Timing differences below are not evidence favoring either threshold; neither run reached its threshold.

Both replays stopped at their cooperative time limit and saved an independently checked prefix. The best new partial certificate contains 11 physical pieces and covers 45.9534%. It is not an improvement over the preserved 95.0668% incumbent. The numerical candidates had maximum principal-width aspect ratio about 1.65, but a largest/smallest volume ratio about 10.37; volume balance still needs work. Those quality measurements describe the numerical candidates, not a fabrication certificate of the exact prefix.

This pilot exercises fresh search, actual LP solves, exact recipe replay, truthful partial handoffs, and full-remainder completion attempts. It does not yet compare completion difficulty at 80% versus 90%. A meaningful comparison needs enough numerical/replay budget to reach those certified handoffs, followed by equal completion budgets. Broader reopening is regression-tested and enabled by the default two-round configuration; this one-round smoke pilot did not run that second attempt.