Memo search solver: MILP over the memo for all cost models #888

Problem, by example

The memo-group search (#879) needs a solver: given the memo (groups, implementation candidates, local prices, coupling sites), pick one implementation per group and one value per coupling site at minimum cost.

Take three quantile queries over one metric that may share a DDSketch build: Qa with relative error 0.01, Qb with 0.02, Qc with 0.05. They run under two cost models:

• Cost model 1 (usage over time, additive). The cost of a choice is a sum of local prices. Threshold enumeration on the shared build's size (sized for 0.01, 0.02, 0.05, or not shared), then dynamic programming over the other groups, finds the optimum. It is fast and predictable.
• Cost model 3 (cluster capacity, say 256 GB of memory). Two groups whose cheapest choices use 200 GB each are each feasible alone and infeasible together. The DP must keep a Pareto frontier over cost, peak memory, cores, disk and worst latency per group, and check the capacity when frontiers combine. That is hand-written multi-dimensional bookkeeping. A capacity limit is a single linear constraint in a mixed-integer linear program (MILP).

Why it matters

The two solvers trade off differently, and the memo they read is the same:

MILP sketch over the memo:

x[g,i] in {0,1}   group g uses implementation i
s[k,t] in {0,1}   coupling site k takes threshold t (shared size, pane grid, raw horizon, scan labels)
r[g,k] in {0,1}   group g reads shared site k

min  sum cost[g,i] x[g,i] + sum sitecost[k,t] s[k,t] + read costs
s.t. each group: exactly one implementation
     an implementation's child groups are implemented
     r[g,k] <= sum over thresholds t no stricter than g's requirement of s[k,t]
     raw horizon: indicator constraints for the longest raw-reading reader
     cost model 2: peak terms; cost model 3: capacity <= limit
     latency per evaluation <= max_latency_ms and <= repeat interval (path sums)

Proposal

Decided on 2026-10-22:

1. Phase 1 (cost model 1): DP + threshold enumeration + branch and bound, as in the joint-planning-search design. It is additive, predictable and dependency-free, and it is what the memo workers are building.
2. Cost models 2 and 3: a MILP solver over the same memo, replacing the hand-written Pareto frontiers. This comes after the memo switch-over.
3. A cross-check mode: solve cost model 1 with both solvers and assert equal optimal cost on the equivalence workloads. This is an extra correctness oracle for the DP.

The memo generation (groups, implementations, local prices, coupling sites) is shared by both solvers.

Scope and acceptance

• In scope: a MILP model builder from the memo; a good_lp/HiGHS backend behind a feature; solver selection by cost model; the cross-check mode.
• Out of scope: approximate solving. A time limit that ends with a nonzero gap is reported as such, never as optimal.
• Acceptance:
  • cost models 2 and 3 select the same plan as --exhaustive on small workloads, including a peak case and a capacity case;
  • the cross-check passes on every joint_search_equivalence workload;
  • planning time for the paper workloads under cost models 2 and 3 is reported.

Status and related work

• Depends on the memo-group search (Tracking: plan every whole evaluation workload within 3 minutes (exact pruning, memo-group search) #879); design in the joint-planning-search document (docs: ASAPPlanner memo-based joint optimization with MILP #776).
• Until this lands, cost models 2 and 3 plan with the current search, as a logged per-run choice.
• Related: Planning roadmap: move ASAPQuery planning into ASAPPlanner, MILP plan selection over shared DAGs, benchmark-based accuracy #671 (planning roadmap, MILP plan selection over shared DAGs).