Stage 3 MILP: implement the formulation variables x, y, z, t and rows (A)–(I) as named code over explicit edges #1204

Example

Same queries as #1201: A (rank error) meets its target with the KLL state at k=200 or k=345; B (relative-error ratio) reads a DDSketch state, whose alpha must be small enough for both operands (constraint (K) below); A and B both run every 10 s. Take B's producer $u$ = SummaryAgg(DDSketch alpha=a).

• Formulation: one variable $x_u$, two edge variables $y_{u,c,i}$ (B's two operands), cost $w_u x_u$ counted once.
• feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144 MILP today:
  • one p[q_A, u] and one p[q_B, u] for the query-time, not-kept candidate, each priced per context;
  • one x[m] for the kept (MatAtQuery) candidate, read across the boundary by p[q, m] ≤ x[m];
  • no edge variable: an edge is p[ctx, c] ∧ p[ctx, u], with constraints 2–3 (one candidate per result slot per context, and validity);
  • a query-time, not-kept $u$ read by A and B runs twice, once in each context. The formulation's fixed $w_u$ counts it once.
• Decided below:
  • a (QueryTime, None) $u$ gets a context index. Contexts are per evaluation schedule (decided 2026-11-06): A and B, both every 10 s at phase 0, share one context $\kappa$, so it is one $x_{\kappa,u}$, cost $0.1C$. Were B every 15 s, it would be $x_{\kappa_{10,\text{s}},u}$ and $x_{\kappa_{15,\text{s}},u}$, cost $0.1C + 0.067C$;
  • a $u'$ = (QueryTime, OneEvaluation) belongs to one evaluation context: A and B, both every 10 s at phase 0, are evaluated together in one context $\kappa$, so it is one $x_{\kappa,u'}$, cost $0.1C + C_{\text{retain}}$ (decided 2026-11-06: no schedule property).

This issue makes each of the formulation's variables and constraints a named part of the Stage 3 code. Where the code must differ (execution contexts), the issue states the difference in the formulation, not only in the code.

Representation, rules, enumeration

• (a) Representation. No change to the memo. The MILP's variables mirror it:
  • $x_v$ per candidate, with a context index for $\ell$ = None and OneEvaluation candidates;
  • $y$ per admissible edge;
  • $z$, $t$, and $h_v$ per AcrossEvaluations candidate.
• (b) Rules. None. Stage 3 only reads the memo and the edges.
• (c) Enumeration. This issue is the enumeration.
  • DAGs are not listed one by one. The MILP over $x$ and $y$ with constraints (A)–(I), (K) and (R) selects the cheapest DAG. Latency (L) and resource budgets (B) are out of scope (items 5 and 6).
  • decode.rs turns ${x = 1}$ and ${y = 1}$ into DagOfSelectedCandidates.
  • The reference enumerator checks the result on small workloads.

Formulation

Variables:

• $x_v$: candidate $v$ is selected;
• $y_{u,c,i}$ for $(u,c,i) \in \mathcal E$ (Producer–consumer edges (u, c, i): make the edge set explicit after Pass 2 and Stage 2, with α^log and α^phys, as the domain of y_{u,c,i} #1201);
• $z_{q,v}$: $v \in G_q$ gives query $q$'s result;
• $t_v$: topological rank.

Constraints:

• (A) $\sum_{u \in P_{c,i}} y_{u,c,i} = x_c$;
• (B) $y_{u,c,i} \le x_u$;
• (C) $\sum_{v \in G_q} z_{q,v} = 1$;
• (D) $z_{q,v} \le x_v$;
• (E) $t_u + 1 \le t_c + |\mathcal C|(1 - y_{u,c,i})$;
• (F) $x_v \le \sum y_{v,c,i} + \sum z_{q,v}$;
• (G) $y \le \alpha^{\log}$;
• (H) $y \le \alpha^{\mathrm{phys}}$;
• (I) domains.

Objective (before items 1 and 4 below refine it): $\min \sum_{v} w_v x_v$, where
$$w_v = C_{\text{read}}(v) + C_{\text{compute}}(v) + C_{\text{retain}}(v, \ell_v)$$
is fixed before optimization.

Where the code needs more than this formulation.

1. Execution contexts, for candidates with $\ell$ = None or OneEvaluation (decided 2026-11-04; OneEvaluation added 2026-11-06). $w_v$ is fixed only if $v$ runs a fixed number of times. A candidate with $\ell$ = None or OneEvaluation runs once per context that reads it.

   • Assumptions under which this is exact:

     1. Whether a consumer can read a result depends only on that consumer and the result's context, window width or refresh window. It never depends on which other consumers read the result.
     2. A run's cost is fixed. The only consumer-dependent terms are of $\max$ type (longest range, slowest consumer).
     3. A result has no capacity limit on its consumers, and no cost grows superadditively with consumers (contention is not modeled).
     4. Accuracy is composed by worst-case bounds and a union bound, never by assuming that estimates are independent.

     Under these assumptions, merging two runs of the same configuration in the same context never costs more. So at most one run per (candidate, context) is needed. There is no slot model with symmetry breaking, and no separate notion of an instance.

   • No schedule property (decided 2026-11-06). $p^{\mathrm{phys}} = (\tau, \ell)$ (Physical properties: replace Materialization with timing × lifetime (None / OneEvaluation / AcrossEvaluations) and a schedule for shareable results, with r^phys and α^phys #1200). Every tumbling-window grid is anchored at phase 0; width candidates come from the gcd closure of the queries' ranges, steps and phases.

   • AcrossEvaluations candidates: $W^{\mathrm{mat}}v = \rho_v(C{\text{read}} + C_{\text{compute}})$, the fixed cost over the horizon with $\rho_v$ its window builds (one per window, when it ends), is fixed, retention is $\pi_v h_v$ (item 4), and $x_v$ (written $x^{\mathrm{mat}}v$ in the extension), $y{u,c,i}$ stay as written.

   • Candidates with $\ell$ = None or OneEvaluation, at query time (None also at ingestion time). The MILP indexes them by context, $\kappa \in \mathcal K = {\kappa_T} \cup {I_r} \cup {\kappa_m : m \text{ across evaluations}}$. $\kappa_T$ is the evaluation context of $T$ = (QueryRecurrence, RangeEvaluation), the workload's own description of when queries run: every query with equal ones is evaluated in it, and they share its OneEvaluation results (decided 2026-11-06). One-off queries are supported: each is the context of its OneTime recurrence. QueryRecurrence holds an f64 and cannot be hashed, so contexts are deduplicated by equality and ExecutionContextId indexes the list of distinct contexts. $I_r$ is the ingestion pipeline of refresh window $r$, as in feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144. $\kappa_m$ covers a None candidate that is an input of an AcrossEvaluations $m$ and runs in $m$'s computation.

     • OneEvaluation belongs to one evaluation context. Queries with equal recurrence and range evaluation are evaluated together, and that evaluation's consumers share the result. It runs when the context runs, chosen through $x_{\kappa,v}$ as for $\ell$ = None. Sharing across differently scheduled queries through a gcd schedule is dropped: it is rarely beneficial and wastes runs.
     • Variables: $x_{\kappa,v}$, at cost $\rho_\kappa, c_{\kappa,v}$ ($c_{\kappa,v}$ is one execution in context $\kappa$, $\rho_\kappa$ the executions of $\kappa$ over the horizon, from the existing evaluation counting in asap_cost::execution_demand; a one-off query's is its invocations), and $y_{\kappa,u,c,i}$.
     • Reading another None or OneEvaluation candidate: only within the same $\kappa$, so $y_{\kappa,u,c,i} \le x_{\kappa,u}$.
     • Reading an AcrossEvaluations $u$: $y_{\kappa,u,c,i} \le x_u$, admissible only if $u$ delivers_on $\kappa$: for its tumbling width $w$, $w$ divides every evaluation time of $\kappa$: the evaluation grid $\gcd(\text{interval}, \text{step}, \text{phase})$ of FixedIntervalAt, every Scheduled time, or a OneTime query's time; never for FixedInterval without a phase, OneTime without a time, EstimatedRate or Unknown (PhysicalCandidate::delivers_on, below). This is not part of $\alpha^{\mathrm{phys}}$, which checks timing and lifetime only; Stage 3 checks it per context, so $y_{\kappa,u,c,i}$ exists only if the producer delivers on $\kappa$.

   • Rejected:

     • (b) a None or OneEvaluation candidate may be read by one context only. Making $w_v$ fixed then needs a copy per query, the duplication Stage 3 MILP vs the memo formulation: one choice costs several binaries, sizes and targets are groups, and the group graph is cyclic #1199 describes.
     • A context in every candidate (Stage 2 copies None and OneEvaluation candidates per context). The copies differ only in who reads them, which is Stage 3's choice; it is the same duplication.
     • A general slot model (instances numbered per configuration, with restricted-growth symmetry breaking). It is not needed under assumptions 1–4.

2. ReaderConstraint is deleted, and constraint (J) with it (decided 2026-11-06). Stage 2's ReaderConstraint (graph.rs:18) has four variants; none stays.

   • Replaced by the per-context alignment check (delivers_on):
     • IncompatibleOutputs. Today it comes only from a chain materialized across evaluations whose queries differ in interval or phase (builds_one_tumbling_window_per_evaluation). With grids anchored at phase 0 and widths from the gcd closure of ranges, steps and phases, a width both can read is offered.
       • Example: two 10 s queries at phases 0 s and 5 s both read one 5 s chain.
       • feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144 allows only one of them (l + r ≤ 1, model.rs:1372). Add a regression test.
     • AllowedOutputs, which is per consumer.
   • Left to the cost model: MinimumQueryReaders (keep a candidate only if enough queries reach it) and HighestSharedQueryMaterialization (materialize where sharing stops). Materializing for one query, or below the point where sharing stops, costs more and is not chosen. There is no constraint (J) and no reach variable $a_{q,v}$.

3. Accuracy at the query root, constraint (K) (decided 2026-11-04; encoding 2026-11-06). Sizes $\theta$ come from a predefined list, so each candidate's own error bound $\varepsilon^{\mathrm{loc}}c$ and failure probability $\delta^{\mathrm{loc}}c$ are constants (zero for an exact operator). Accuracy is not an edge requirement: (G) covers only the parameter floor $\boldsymbol\theta^{\min}$, derived from the validity and pruning caps (Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203), not a budget share. Path factors depend on which edges are selected, so (K) does not use per-path terms or a reach variable $a{q,u}$. Each candidate carries continuous error bounds $E_c$ and $D_c$, with big-M on the selected edge:
   $$E_c \ge \varepsilon^{\mathrm{loc}}c + \sum_i \beta{c,i} F{c,i}, \qquad F_{c,i} \ge E_u - M_{c,i}(1 - y_{u,c,i}) \quad \forall (u,c,i)\in\mathcal E,$$
   $$D_c \ge \delta^{\mathrm{loc}}c + \sum_i H{c,i}, \qquad H_{c,i} \ge D_u - (1 - y_{u,c,i}) \quad \forall (u,c,i)\in\mathcal E,$$
   $$E_v \le \varepsilon_q + M_q(1 - z_{q,v}), \qquad D_v \le \delta_q + (1 - z_{q,v}) \qquad \forall q,\ v \in G_q \tag{K}$$

   • $E_c, F_{c,i}, D_c, H_{c,i} \ge 0$ are continuous. $\beta_{c,i}$ is the local factor of consumer $c$'s input $i$, from error_propagation (Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203), defined per input and output metric (metric rule: when the metric cannot be converted there is no edge, $\alpha^{\log} = 0$). Example: sum by (job) over 10 series multiplies an absolute error by up to 10.
   • $M_{c,i}$ is any upper bound on $E_u$ over the producers of input $i$; $M_q$ likewise for the root. By (A), exactly one $y_{u,c,i} = 1$ per selected input, so $F_{c,i}$ is the chosen producer's bound.
   • Worst-case counting affects the bounds only, not cost. A producer reached by two paths contributes on both, and a failure event reached twice is counted twice. The objective counts each selected candidate once through $x_v$. This can only make the MILP pass over a cheaper plan that would meet the target; it never accepts one that does not.
   • Under contexts (item 1), the variables are indexed per context, $E_{\kappa,c}$, and the edges are $y_{\kappa,u,c,i}$.
   • Composition. Errors add in the worst case, and failure probabilities by a union bound. No independence is assumed (assumption 4).
   • Non-linear operators (ratio, product) use a conservative linear bound valid when each $\varepsilon$ is at most a cap, e.g. relative errors $\varepsilon_X + \varepsilon_Y$ plus a second-order margin. The cap enters the consumer's parameter floor $\boldsymbol\theta^{\min}$ (LogicalRequirements::parameter_floor_for_required_accuracy, Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203): an edge from a producer below the floor has $\alpha^{\log} = 0$.
   • Where β, λ and the caps come from (decided 2026-11-05). Each local factor $\beta_{c,i}$ is read from an operator and its arguments (error_propagation, Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203). $\lambda_{q,c,i}$ is the product of the $\beta$ factors along $q$'s expression from input $i$ of $c$ to $q$'s root, summed over paths; it is used only for the pruning caps. Every consumer, linear ones included, also gets a pruning cap $\max_q \varepsilon_q / \lambda_{q,c,i}$, folded into its parameter floor $\boldsymbol\theta^{\min}$: edges whose error alone breaks every target they could serve are not in $\mathcal E$. It removes no feasible plan; (K) still decides.
   • Exact inputs have $\varepsilon = \delta = 0$.
   • Example. $q = X - Y$ with $\varepsilon_q = 0.01$ may pick X at $\varepsilon = 0.008$ and Y at $0.002$. An even split cannot express this (1, below).
   • Rejected: budget shares in $\theta$ (accuracy_budget_parts, feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144's A[q, parts]).
     1. It only splits evenly.
     2. It copies consumers per share count.
     3. It needs a consistency constraint tying a query's share count to how many of its inputs are approximate.
   • Replaces feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144's constraint 8 and its N[q], A[q, parts] variables, and removes the reach $a_{q,u}$ from (K). accuracy_budget_parts is deleted (Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203).

4. Retention amount $h_v$ (decided 2026-11-04). How much an AcrossEvaluations candidate retains depends on which consumers select it.

   • Examples:
     • a tumbling-window chain kept across evaluations retains as many windows as its longest selecting query needs: 30 for a 5m query, 6 if only a 1m query is left.
   • Variable. A continuous $h_v \ge 0$ per AcrossEvaluations candidate $v$, with one constraint per edge out of $v$:
     $$h_v \ \ge\ \text{need}{c,i}\cdot y{v,c,i} \qquad \forall (v,c,i)\in\mathcal E,\ \ell_v=\mathrm{AcrossEvaluations} \tag{R}$$
     • $\text{need}_{c,i}$ is a constant per edge, fixed before optimization. For an AcrossEvaluations chain read by $(c, i)$, it is the number of tumbling windows $(c, i)$ reads, including its offset.
     • The need is the time horizon the served queries read (decided 2026-11-06). For an edge into a consumer in context $\kappa$, $\text{need}_{\kappa,v,c,i}$ is how much of $v$'s output those queries read, e.g. a 5m range over 10 s windows needs 30 windows. It is a constant per edge, so (R) stays linear.
     • Query latency is ignored for now. A OneEvaluation result held until its slowest consumer finishes would need that consumer's latency $L_c$, which belongs to the out-of-scope latency model (item 5). Until then a result is assumed read when its evaluation starts, and a OneEvaluation result's storage within its evaluation is part of $c_{\kappa,v}$. The PR that implements (R) (Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207 PR 7) states this assumption.
     • For a consumer with $\ell$ = None or OneEvaluation, $y$ carries its context, as in item 1.
   • Objective. The cost splits into a fixed part and a retention part $\pi_v h_v$ priced per unit of $h_v$:
     $$\min\ \sum_{v:,\ell_v=\mathrm{AcrossEvaluations}} W^{\mathrm{mat}}v, x^{\mathrm{mat}}v ;+; \sum{\kappa, v:,\ell_v\in{\mathrm{None},\mathrm{OneEvaluation}}} \rho\kappa, c_{\kappa,v}, x_{\kappa,v} ;+; \sum_{v:,\ell_v=\mathrm{AcrossEvaluations}} \pi_v, h_v,$$
     where:
     • $W^{\mathrm{mat}}v = \rho_v(C{\text{read}} + C_{\text{compute}})$ is the fixed cost of an AcrossEvaluations candidate over the horizon;
     • $c_{\kappa,v}$ is one execution in context $\kappa$, and $\rho_\kappa$ the executions of $\kappa$ over the horizon;
     • $\pi_v$ is the retention cost per window or per second held, for $v$'s configuration and medium.
   • Why it is exact. Each $\pi_v > 0$, so the minimum sets $h_v = \max$ of the selected consumers' needs. That is the consumer-dependent term of $\max$ type in assumption 2.
     • A merged result's retention $\max(a, b)$ never exceeds two separate results' $a + b$, so "at most one candidate per configuration" still holds.
   • Non-linear retention cost. If the retention cost is not linear in $h_v$ (tiers, a medium switch), $h_v$ is replaced by [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095's per-length indicators $\pi[m, \ell]$ over the possible needs, which is exact for any cost per length.
   • Raw data retention ([Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095 $v[\text{src}, \ell]$) has the same form: $h_{\text{src}} \ge \text{need}\cdot y$ over the scans that read it.
   • Maps to feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144: $S[m]$ (windows kept) and $H[m]$ (hold time) are $h_v$; $\pi[m,\ell]$ is the non-linear form.

5. Latency, constraint (L): out of scope (decided 2026-11-06). Latency needs an execution and critical-path model that the concepts doc does not define; it needs its own design later, and this issue implements no (L) variables or constraints. The 2026-11-04 draft below is kept only as input to that design. It follows feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144's constraint 7 and asap_cost::plan_cost's definition. A query's latency is:

   • its request time;
   • plus the work of every query-time run it reaches, each counted once;
   • plus the longest compaction among the ingestion-time states it reaches.

   With $d_v$ the latency of one run of $v$ (a constant from the cost model) and $\bar L_q = \min(\texttt{max_latency_ms}q, I_q)$ (latency_bound_ms):
   $$
   \begin{aligned}
   & L_m \ \ge\ d_m x_m + \textstyle\sum{v:,\ell_v=\mathrm{None}} d_v, x_{\kappa_m,v} && \forall m \text{ kept},\ \tau_m=\mathrm{QueryTime}\
   & T_{q,m} \ \ge\ L_m - \bar L_m,(1-a_{q,m}) && \forall q,\ m \text{ kept at query time}\
   & K_q \ \ge\ c_m, a_{q,m} && \forall q,\ m \text{ kept at ingestion time}\
   & L_q \ \ge\ d^{\text{req}} + \textstyle\sum_{v:,\ell_v=\mathrm{None}} d_v, x_{\kappa_q,v} + \sum_m T_{q,m} + K_q, \qquad L_q \le \bar L_q && \forall q
   \end{aligned} \tag{L}
   $$

   • Variables:

     • $L_q$: latency of query $q$;
     • $L_m$: latency of a kept query-time result's run;
     • $T_{q,m}$: $m$'s latency counted in $q$, which is 0 unless $q$ reaches $m$;
     • $K_q$: longest compaction;
     • $c_m$: compaction time, a constant.

     All four are continuous.

   • Assumptions:

     • Work adds up. A query's work is summed: one evaluation's runs execute one after another, with no parallelism modeled.
     • Shared runs count once. A kept result's run counts once in each query that reaches it.
     • Ties to (R). $L_c$ is also the hold time of a OneEvaluation result for constraint (R) (item 4).

   • Interval bound. A query without max_latency_ms is still bounded by its interval $I_q$, so one evaluation finishes before the next starts.

6. Resource budgets, constraint (B): out of scope (decided 2026-11-06). Budgets need accounting units that the concepts doc does not define; they need their own design later, and this issue implements no (B) variables or constraints. The 2026-11-04 draft below is kept only as input to that design. This is new: today the planner only prices resource usage (cost model 1) and caps nothing.

   • For each resource $\rho \in \mathcal R$ with a deployment budget $B_\rho$: a generic named resource, e.g. memory held, CPU per second at query time, CPU per second at ingestion, disk held. It keeps the planner deployment-agnostic.
     $$\sum_{v} u^{\text{fixed}}{v,\rho}, x_v + \sum{\kappa,, v:,\ell_v=\mathrm{None}} \rho_\kappa, u_{v,\rho}, x_{\kappa,v} + \sum_{v:,\ell_v\ne\mathrm{None}} \mu_{v,\rho}, h_v \ \le\ B_\rho \qquad \forall \rho\in\mathcal R \tag{B}$$

   • $u_{v,\rho}$ is $v$'s usage of $\rho$ per run, or held, from the same resource usage the cost model already computes (ResourceUsage). $\mu_{v,\rho}$ is the usage per unit of retention $h_v$, e.g. bytes per kept tumbling window.

   • Held memory is summed over all kept results (steady state). Working memory of a run is held only while its evaluation runs. It is bounded per query instead, the same way:
     $$\sum_{v \text{ in } \kappa_q} u^{\text{work}}{v}, x{\kappa_q,v} + \textstyle\sum_m u^{\text{work}}m, a{q,m} \le B_{\text{work}}.$$

     This assumes queries do not run concurrently; concurrent peaks are out of scope.

   • Where the budgets come from. They are inputs of the planner, next to the cost model's unit costs. A missing budget means no constraint.

Data structures and interfaces

crates/plan-selection/src/milp/model.rs:

• variable families named after the formulation: x, y, z, t, each with its index type;
• one function per constraint family (A)–(F), (K) and (R), each citing its constraint in the doc comment;
• the header table lists each variable family and constraint family with its letter.

struct SelectionVariables {
    x_materialized: Vec<Variable>,                                   // x_v, per AcrossEvaluations candidate
    x_in_execution_context: HashMap<(ExecutionContextId, PhysicalCandidateId), Variable>, // x_{κ,v}, per ℓ = None or OneEvaluation candidate
    y: HashMap<(Option<ExecutionContextId>, PhysicalEdgeId), Variable>, // y_{u,c,i}; the context when c is ℓ = None or OneEvaluation
    z: Vec<Variable>,                            // per (output reference, output candidate)
    t: Vec<Variable>,                            // only on cyclic components, as today
    h: Vec<Variable>,                            // h_v, per AcrossEvaluations candidate, continuous
    error_bound: ErrorBoundVariables,            // E_c, F_{c,i}, D_c, H_{c,i}, continuous (per context under contexts)
}
fn input_satisfaction_constraints(...);   // (A)
fn producer_selection_constraints(...);   // (B)
fn query_coverage_constraints(...);       // (C), (D)
fn acyclicity_constraints(...);           // (E)
fn utilization_constraints(...);          // (F)
fn accuracy_constraints(...);             // (K): E_c, D_c, big-M on y, root checks
fn retention_constraints(...);            // (R): h_v ≥ need · y
// (L) latency and (B) resource budgets: out of scope, no functions here.

• Edges. (G) and (H) are not constraints: $y$ exists only on admissible edges (admissible_edges_into, Producer–consumer edges (u, c, i): make the edge set explicit after Pass 2 and Stage 2, with α^log and α^phys, as the domain of y_{u,c,i} #1201).
• Execution context times. For a consumer with $\ell$ = None or OneEvaluation, the times of its context:

pub enum ExecutionContext {
    /// κ_T: the evaluation of every query with this recurrence and range evaluation.
    Evaluation { recurrence: QueryRecurrence, range_evaluation: Option<RangeEvaluation> },
    /// I_r: the ingestion pipeline of a refresh window.
    IngestionPipeline(RefreshWindowId),
    /// κ_m: inside an AcrossEvaluations candidate's own computation.
    Materialized(PhysicalCandidateId),
}

/// y_{κ,u,c,i} exists only if `u.delivers_on(memo, &context)`.
impl PhysicalCandidate {
    pub fn delivers_on(&self, memo: &Memo, context: &ExecutionContext) -> bool;
}

• groups.rs: ResultSlot and the e binaries exist so that $p \wedge p$ identifies an edge, and feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144's constraint 2 ("one candidate per slot per context") exists for the same reason. With explicit $y$, they are expected to go away; the PR confirms nothing else (e.g. self-read depth) still needs them.
• decode.rs: reads $y$ to build DagOfSelectedCandidates::edges directly.

Current vs proposed

Scope and acceptance

In scope:

• Stage 3 variable and constraint naming;
• explicit $y$ on admissible edges;
• removing ResultSlot, e and feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144's constraint 2;
• the formulation text for contexts (None and OneEvaluation candidates), assumptions 1–4, (K) with local factors and the non-linear bound, and deleting ReaderConstraint;
• removing N[q], A[q, parts] and feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144's constraint 8;
• the regression test: two 10 s queries at phases 0 s and 5 s both read one 5 s chain.

Out of scope:

• latency (L) and resource budgets (B), including budget inputs: each needs its own design later;
• the edge set itself (Producer–consumer edges (u, c, i): make the edge set explicit after Pass 2 and Stage 2, with α^log and α^phys, as the domain of y_{u,c,i} #1201);
• property types (Physical properties: replace Materialization with timing × lifetime (None / OneEvaluation / AcrossEvaluations) and a schedule for shareable results, with r^phys and α^phys #1200, Logical memo candidate as (one operator over groups, logical properties θ) with a requirement per input; no private nodes #1203);
• solver tuning (Planning is about 20x slower since the full tumbling-window-width domain (#1185) #1197).

Acceptance:

• Deletes what it replaces in the same PR, with no dead code, fallback, flag, shim or reuse of an old abstraction; the PR body lists what it deleted (Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207, Policy).
• Order: see Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207, "Order (rewritten 2026-11-06: interfaces first, baseline before extensions)". This issue's parts are PRs 0, 6, 7 and 8.
• Plans. Every corpus and sketch-plan snapshot selects a plan of the same cost.
• Model size. Report the MILP size (variables, binaries, constraints) per snapshot before and after. If explicit $y$ grows the model by more than 2×, we decide here, before merging, whether to keep the implicit encoding with a documented mapping.
• Tests. asap-plan-selection --lib passes.

Related

• Tracking: Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207.
• Stage 3 MILP vs the memo formulation: one choice costs several binaries, sizes and targets are groups, and the group graph is cyclic #1199: the full comparison of feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144 against this formulation.
• [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095 / feat(plan-selection): group selection MILP over execution contexts as Stage 3's default search (#1095) #1144: execution contexts and constraints 1–10.
• Producer–consumer edges (u, c, i): make the edge set explicit after Pass 2 and Stage 2, with α^log and α^phys, as the domain of y_{u,c,i} #1201: edges; Physical properties: replace Materialization with timing × lifetime (None / OneEvaluation / AcrossEvaluations) and a schedule for shareable results, with r^phys and α^phys #1200: run kinds.