Skip to content

Stage 3 MILP: scaling the objective by its largest coefficient lets HiGHS stop 5e-8 relative above the optimum (RangeHeavy-8users L1 quantiles) #1356

Open

Description

@zzylol

Example

The paper's RangeHeavy-8users L1 quantiles component (24 quantile_over_time queries over data, every 60 s and every 300 s, relative error 0.05, raw data kept, unit costs tools/dag-viewer/cost-inputs/aws-fargate-us-east-1.json):

asap_planner --workload quantiles.json --deployment-capabilities caps_raw.json \
  --cost-inputs aws-fargate-us-east-1.json --run-until stage3

Stage 3 selects plans whose costs differ by about 5e-8 relative depending on how the same model is written down:

Model Selected plan cost per second
contexts that are copies share their variables (default) 9.1106875266e-5
every context has its own variables 9.1106870769e-5 (4.9e-8 relative cheaper)

Both models have the same optimum. Forcing the second model's selection for the 300 s context into the first model is feasible and reaches 9.11068707685e-5, so HiGHS stops at a worse plan in the first model.

What should happen: the selected plan is the optimum to within the relative tolerance (1e-12) the rest of Stage 3 uses, whatever the model's size.

Why it happens

solve_selection (crates/stage3-plan-selection/src/milp/model/mod.rs) scales every objective coefficient so that the largest kept coefficient is 1,000, because HiGHS's tolerances are absolute:

let scale = match largest > 0.0 && largest.is_finite() {
    true => 1_000.0 / largest,
    false => 1.0,
};

Here the largest kept coefficient (0.077 per second) belongs to an execution the optimum does not select. Scaled by 1,000 / 0.077, the whole optimum is only about 1.18 scaled units, and the gap between the two plans is 5.8e-8 scaled units. That is below HiGHS's absolute feasibility and MIP tolerances (1e-7 and 1e-6 by default), so with mip_rel_gap and mip_abs_gap set to 0 HiGHS still accepts either plan as optimal. Which one it returns depends on the model's shape, which is why the two equivalent models disagree.

The same numbers appear before the copy check was changed, so copies did not cause this; they only change the path HiGHS takes.

Proposal

Scale the objective by the cost of a plan the MILP can reach instead of by the largest coefficient: dearer_than_a_feasible_plan already computes a feasible plan's cost per second (feasible_plan_cost_per_second). With scale = 1_000.0 / feasible_plan_cost, the optimum is between 0 and 1,000 scaled units, so HiGHS's absolute tolerances become about 1e-9 relative to it. An execution dearer than that plan is already left out, so the kept executions' costs stay within a small multiple of the scale. (Retention coefficients are per retained millisecond, so they need their own check.)

Alternatives: keep the coefficient scale and lower HiGHS's mip_feasibility_tolerance/primal_feasibility_tolerance (slower and fragile), or re-price the selected plan's neighbours after the solve (more code).

Scope and acceptance

  • In scope: the objective's scale in solve_selection and the raw-data rows that share it.
  • Test: a unit test in milp/model/tests.rs with a left-in but unselected execution whose cost is 1e3 times the optimum and two plans 1e-8 relative apart; it must select the cheaper one with and without context copies.
  • On RangeHeavy-8users L1 quantiles both models give the same plan cost to 1e-12.

Related

Activity

  1. added
    bugSomething isn't working
    optimizerWorkload optimization and plan selection
    on Nov 15, 2026
  2. zzylol commented on Nov 16, 2026

    @zzylol
    ContributorAuthor

    Accuracy constraint (K) (#1207 PR 8, #1238) touches this issue in two places. Whoever fixes the objective scale needs both.

    1. With an accuracy target, (K) already lowers HiGHS's tolerances. (K)'s limits can be far smaller than HiGHS's absolute default of 1e-7. For example, δ = 0.01 over a whole result of 1e4 values is 1e-6 per value. So when a query has a target, solve_selection sets the primal and MIP feasibility tolerances to min(1e-7, 1e-3 · smallest positive target limit), but never below 1e-10, the lowest value HiGHS accepts (AccuracyRules::feasibility_tolerance).

    • This is the "lower the tolerances" alternative the issue lists, but only for workloads with targets. Those runs therefore no longer use the defaults the issue's numbers assume.
    • (K)'s rows are not multiplied by the objective scale, so a new objective scale leaves them alone.
    • I also tried scaling (K)'s rows by their limits and keeping the default tolerances. It was correct but much slower:

    RangeHeavy-8users, one pinned core per variant, one run each, host load 30–48, all five variants run in parallel:

    (K) rows Tolerances Stage 3 wall time Plan cost per second
    unscaled 1e-10 (previous head) 24.2 s 1.77767993689469e-4
    unscaled derived, 1e-9 (#1238 now) 26.3 s 1.77767993688512e-4
    unscaled defaults 39.9 s 1.77767993689837e-4
    scaled by limits defaults 99.3 s 1.77767993689984e-4
    scaled by limits 1e-10 82.8 s 1.77767993690418e-4

    The plans differ by up to 8e-12 relative: this issue's tolerance effect. With the derived tolerance, the median of 3 runs on a quieter host (load 14) is 13.6 s, against 9.7 s on main. Main's plan misses its accuracy targets.

    2. feasible_plan_cost_per_second now returns None exactly on some workloads with targets. The greedy plan reads the cheapest readouts. Two of them can each meet their own level and still compose above the target, as in a ratio of shared quantiles (RangeHeavy-8users, and p90, p50 and p90/p50 at relative 0.05). Using such a plan as a bound could prune the readouts the optimum needs, so #1238 returns None when the greedy plan misses (K). The proposed scale = 1_000 / feasible_plan_cost then has no value on those workloads. It needs a fallback, either the current coefficient scale or a greedy plan that meets (K), and a test with a target whose greedy plan misses (K).

  3. zzylol commented on Nov 16, 2026

    @zzylol
    ContributorAuthor

    Another instance found while reviewing the #1207 accuracy constraint (K) PR: workload h01q_rel10_exact20_qt from the enumeration-oracle set selects a plan 1.4e-9 relative dearer than the enumerated optimum (and h03n_rank60_rel120_noraw 1.3e-11). Both have only large accuracy limits, so HiGHS runs at its default tolerances. Forcing a 1e-7 feasibility tolerance on every workload with a target fixed h03n but not h01q and made c09 17% slower, so it was not kept. Same objective-scale effect as described above.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't workingoptimizerWorkload optimization and plan selection

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions