Repository navigation
Description
Example
c22_topk_count_over_gauge on #1237 (head baab8969a), release asap_planner --run-until stage3, bundled HiGHS 1.15.0, one thread:
| value | |
|---|---|
greedy upper bound (feasible_plan_cost_per_second) |
0.368/s |
| MILP optimum | 0.0079/s |
executions left out by dearer_than_a_feasible_plan |
none that change the model |
| presolved model, #1236 → #1237 | 553 → 2,468 rows |
| solve time, median over seeds 0–4, #1236 → #1237 | 0.46 s → 1.69 s |
The bound is 47× the optimum. Others: c16 1.86/s against 0.050/s (37×), o11y_q19 53.2/s against 1.96/s (27×). On #1236 the bound left out 842 of 997 executions on this family; on #1237 it leaves out almost nothing, so c18/c22/c23 are 2.4–3.7× slower (+0.7–1.2 s) and c24 goes from 27 ms to 412 ms, all with the same objective.
Why it happens
cheapest_trees(milp/upper_bound.rs) costs a tree as own execution cost plus its inputs' trees. It ignores retention: the least π_v h_v that (R) forces on a selected execution. The greedy plan therefore picks trees that are cheap to run but expensive to retain, andselection_cost_per_secondof that plan, which does charge retention, is far above the optimum.dearer_than_a_feasible_plancompares own cost + least retention + Σ min(0, edge) against that loose bound, so almost nothing is over it.
Proposal
- Retention-aware greedy trees. In
cheapest_trees, add each execution's least retention cost (π_v × least need over its uses, already computed indearer_than_a_feasible_plan) to its tree cost, so the greedy plan stops choosing high-retention trees. This only changes which feasible plan the bound uses; it stays a valid upper bound. - A lower bound that handles shared producers, if pruning by subtree cost is wanted. A tree cost that sums each input's tree independently counts a producer shared by two inputs twice.
Pruning by the cheapest-tree cost, as first worded, is unsound. Tried on #1237 (seed 0, every review workload): replacing the per-execution lower bound with tree_cost + least retention made n05_sql_avg_window (avg as sum/count over the same scan) and n10_sql_minmax_window infeasible: the double-counted shared scan pushed an execution of the optimum over the bound. It also pruned nothing on c16/c22/c24, because the bound itself is loose. A sound variant must not double count, for example the maximum over the inputs' trees in place of their sum, or a tree cost over the DAG with each producer once.
Scope and acceptance
- In: (1); (2) only with a proof that the bound is a lower bound when inputs share producers.
- Acceptance: on c22 the greedy bound is within a small factor of the optimum and the presolved model is back near refactor(stage3): baseline selection MILP and its PhysicalASAPDAG; executor θ, native chains and a time-indexed store (#1207 PR 6) #1236's size; n05 and n10 keep their optimum; the objective is unchanged on the round-4 review set and the 34
tools/dag-viewerexamples. - Expected gain (not measured): recovering the c18/c22/c23/c24 regressions and the tiny-workload overheads, a few seconds over the 197-workload review set. A tighter bound would also make scaling the objective by the bound (instead of the largest coefficient) usable.
Status and related work
- Follow-up "F5" from the refactor(stage3): select over execution contexts: x_{κ,v}, y_{κ,u,c,i}, h_v and constraint (R) (#1207 PR 7) #1237 efficiency reviews; reworded in round 2 after the unsound result above; approved as a follow-up 2026-11-14.
- Related: refactor(stage3): select over execution contexts: x_{κ,v}, y_{κ,u,c,i}, h_v and constraint (R) (#1207 PR 7) #1237, Tracking: implement the optimization formulation (memo candidates, properties, edges y_{u,c,i}, MILP) as named code per stage #1207, [Feature] Stage 3: no execution-scope copies, exact candidate-level MILP, one cost formula #1095.
Activity