memo-milp: certify whole evaluation workloads within 300 s #927

Problem, by example

Plan the RollupHeavy paper workload whole with the MILP search, raw data retained, fargate prices, guarantees enforced, 280 s limit:

stage_pipeline --workload rollupheavy.workload.json --table ... \
  --deployment-capabilities '{"raw_data_retained":true,"query_time_results_retained":false}' \
  --cost-model aws-fargate-us-east-1 --enforce-accuracy-guarantees \
  --search memo-milp --milp-time-limit-s 280

After the memo-milp PR-B merge (measured on 0f8bf09, shared host) every whole workload returns a plan and its gap within 300 s, but none is certified:

Wanted: each whole workload certified (gap <= 1e-4) against --exhaustive or the legacy search within 300 s wall.

Why it happens

• Round-1 solves take most of the budget. On the big clusters one HiGHS solve takes 200–245 s, so the loop runs 1–10 rounds. RangeHeavy never gets past the warm start.
• The root relaxation is weak. The model leaves some cost terms to lazy term cuts: held memory of shared query-time builds, the ingestion-time copy of a built-once group, and per-consumer multiplicity of scans and builds (Stage 3's x 0.0333/s, which no cut charges yet). The first-round bound is therefore far below the incumbent. Example: j839 root bound 0.10 vs 0.94 scaled.
• Clusters do not split these workloads. RangeHeavy's queries all read one metric, so it is one cluster.
• Some valid choice sets are cut one per round on accuracy misses. See the decode/pair-rule issue.

Proposal (options, not yet chosen)

1. Static model terms for what the cuts add lazily: held memory of shared builds (in progress on w2/held-once) and ingestion copies.
2. Cuts for per-consumer multiplicity, conditioned on two consumers' reach variables.
3. A tighter root LP relaxation: W2 relaxation work, w2-relaxation-wip.
4. Cheaper round 1: the warm start runs during round 1, and the finish relaxation gets only the time left (perf/memo-warm-start-cheap, review clean, two requested changes open).
5. Column generation (deferred so far).

Scope and acceptance

• In: the memo MILP model, cuts and loop under cost model 1.
• Out: cost models 2/3 (Memo search solver: MILP over the memo for all cost models #888); RangeHeavy without raw data (no Stage 1 plan, known gap B3).
• Acceptance: the four rows above certify (gap <= 1e-4) at --milp-time-limit-s 280 within 300 s wall, with cost equal to the reference. The fixed regression set (q24h60, w840*, i840, j839, rh8-q1h60, t11-5m) keeps its costs.

Status and related work

• 2026-10-23: the user decided that PR-B's acceptance is "plan + honest gap in 300 s, components certify", and that whole-workload certification is this follow-up.
• Part of Tracking: plan every whole evaluation workload within 3 minutes (exact pruning, memo-group search) #879. Related: Memo search solver: MILP over the memo for all cost models #888, planner_fuzz: search for workloads that plan slowly or leave the MILP gap open #917.