Skip to content

Remove unnecessary deadlines and caps in the group selection MILP #1185

Closed

Description

@milindsrivastava1997

Why

The group selection MILP (#1095), which is now Stage 3's default search, is
limited by wall-clock deadlines and hardcoded enumeration caps. The deadlines
make the selected plan depend on machine speed and load: HiGHS can stop at an
incumbent that is not proven optimal, and the warm start tries a different
number of orders on each run. That nondeterminism is behind the flaky tests in
#1067, #1175 and #1180. Several caps also silently make costing inexact or
drop candidates, so the plan that comes back is no longer the optimum of the
model we think we are solving.

Hardcoded deadlines

In the MILP solve (crates/plan-selection/src/milp/model.rs)

  • Warm-start budget (model.rs:1860-1864): the warm start gets ⅕ of the
    time left before the deadline, capped by WARM_START_MOST_TIME.
  • WARM_START_MOST_TIME = 60 s (model.rs:2226): the most time the warm
    start takes. With no deadline, it is the warm start's whole budget.
  • Warm start stops when its budget runs out (milp/warm_start.rs:117, 165):
    how many query orders it tries depends on wall time, so the starting point is
    not reproducible.
  • Time split per part (model.rs:1992-1996): each independent part of the
    MILP gets a share of the remaining time, in proportion to its column count.
  • HiGHS time_limit (model.rs:2155-2165): set to the part's remaining
    time. If no time is left, the solve returns DeadlineReached. If the limit is
    hit, HiGHS returns its incumbent, which is not proven optimal.
  • MOMENT_TO_READ_THE_START_S = 1e-3 (model.rs:2223): the smallest time
    limit HiGHS gets, used when the warm start has already used up the deadline.
  • LP_TIME_LIMIT_S = 300 s (milp/lp_diagnosis.rs:35): the time limit for
    each LP solve in the diagnosis. It applies only when
    ASAP_STAGE3_LP_DIAGNOSIS is set, and diagnosis time is added back onto the
    deadline (model.rs:1893).

Upstream deadlines that limit what the MILP sees

  • DEFAULT_TIME_LIMIT_MS = 30 s (crates/planner/src/run.rs:45): the
    whole planning budget, including Pass 1. It is the source of the deadline
    passed to select_plan_with_milp.
  • SEED_ROUND_SHARE = 4, SEED_ROUND_MAX = 5 s (run.rs:47-48): the seed
    tumbling-window-width round gets ¼ of the remaining budget, but no more than
    5 s.
  • INTERMEDIATE_ROUND_MAX = 5 s (run.rs:50): the most time each expanding
    tumbling-window-width round gets.
  • SEED_ROUND_MIN_REMAINING = 1 s (run.rs:52): if less than this is left
    after Pass 1, the seed round is skipped.
  • Pass 2 memo generation deadline
    (check_generation_deadline,
    crates/logical-asap-optimization/src/pass2/memo.rs:30): every Pass 2 rule
    stops once the deadline passes. As a result, the candidate set the MILP
    receives depends on wall time.

Hardcoded enumeration caps

Caps that make costing inexact or drop candidates

  • MAX_CONTEXTS = 256 (crates/plan-selection/src/groups.rs:131): the most
    contexts (combinations of producer outputs, scan windows and pane retentions)
    one candidate is costed under. Beyond it, only the first 256 are costed and
    the candidate's usage is marked TooManyContexts.
  • MAX_PRODUCER_CHOICES = 256 (groups.rs:239): the most producer choices
    costed for one candidate. Beyond it, the usage is marked TooManyContexts and
    the first costed usage stands for every choice, which is an approximation.
  • MAX_WINDOW_KINDS = 4 (groups.rs:1245, used in milp/cost_terms.rs:578):
    the most window kinds of one scan run for which every union is costed and
    encoded exactly. Beyond it, only the union of all kinds is costed.
  • MAX_COMPOSITIONS = 64 (groups/accuracy_positions.rs:41): the most
    outputs one candidate or query is built as for one set of approximate
    candidates. Beyond it, the set is marked unusable (NotChecked), which
    silently removes options from the search.

Warm-start caps

  • MORE_ORDERS = 30 (milp/warm_start.rs:198): the number of pseudo-random
    query orders the warm start tries after workload order and its reverse.
  • MOST_STEPS_PER_QUERY = 200_000 (warm_start.rs:41): the most derivation
    steps one query's warm-start plan takes before the warm start gives up on it.

Caps that guard against loops that never end (probably keep)

  • MOST_PASSES = 64 (milp/completion.rs:46): the most passes over the
    variables before the completion gives up on reaching a fixpoint.
  • MAX_SHIFTS = 4 (groups.rs:1277): time shifts nested deeper than this
    are not followed when collecting a scan's windows.

Related solver setting

  • HIGHS_THREADS = 4 (model.rs:2220): not a cap, but HiGHS with more
    than one thread is not deterministic. Without a time limit, this matters
    only for tie-breaking among plans of equal cost.

Proposed change

  1. Remove the MILP deadlines: the warm-start time budget, the time split per
    part, and the HiGHS time_limit. The solve then always runs to proven
    optimality, and the warm start is bounded by count (MORE_ORDERS) alone.
  2. Decide whether the upstream deadlines (run.rs rounds, Pass 2 generation)
    are removed here or in a follow-up. If they are removed, the round machinery
    (seed and expanding tumbling-window-width domains) may no longer be needed.
  3. For each inexact-costing cap (MAX_CONTEXTS, MAX_PRODUCER_CHOICES,
    MAX_WINDOW_KINDS, MAX_COMPOSITIONS), either remove it or replace the
    silent fallback with an explicit error.
  4. Keep the caps that stop loops that never end (MOST_PASSES, MAX_SHIFTS,
    MOST_STEPS_PER_QUERY).

Acceptance

Activity

  1. milindsrivastava1997 commented on Nov 3, 2026

    @milindsrivastava1997
    CollaboratorAuthor

    For part 2: #1096 defers three Stage 1 items until part 2 lands, since part 2 rewrites the same code (scope: #1096 (comment)):

    • thinning check_generation_deadline calls (part 2 deletes them),
    • the _in_domain / _before wrapper chains in pass2/memo/window_candidates.rs and shared_configurations.rs (likely gone with the domain rounds),
    • splitting rules/rollup.rs add_rollup_candidates.

    Also, #1096 is moving pass2/memo/groups.rs and candidates.rs into pass1/ and adding a test that forbids production pass1↔pass2 imports, with check_generation_deadline as the one allowed exception. Part 2 can delete that exception.

  2. added a commit that references this issue on Nov 4, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions