Skip to content

Optimizer: mip_assign (good_lp + HiGHS) and asap-optimizer-cli --solver greedy|mip #761

Closed as not planned
Closed as not planned
Optimizer: mip_assign (good_lp + HiGHS) and asap-optimizer-cli --solver greedy|mip#761
Assignees
milindsrivastava1997
Labels
asap-plannerenhancementNew feature or request

Description

@milindsrivastava1997
milindsrivastava1997
opened on Oct 4, 2026

Change

Add mip_assign to asap-planner-rs/src/optimizer/: a facility-location MILP using good_lp + HiGHS, ported from sketch-bench#129's rqe-optimizer/src/milp.rs.

  • Candidate pool: union of per-item enumerate_candidates outputs, deduplicated by config.
  • Variables: z[i,g] (item i served by g), u[g] (g deployed). Constraints: Σ_g z[i,g] = 1, z ≤ u, u ≤ Σ_i z[i,g].
  • Objective: Σ_g u[g]·ingest_cost(g) + Σ z[i,g]·freq_i·query_cost(i,g) from cost_model (no peak-memory variable; see Optimizer MILP: explore memory as a hard bound instead of a weighted cost term #750).
  • --milp-time-limit-secs: on timeout use the best incumbent and log the gap; no incumbent → error.
  • asap-optimizer-cli --solver greedy|mip.
  • Test: mip_cost ≤ greedy_cost under identical weights; equal when no sharing is possible.
  • Add HiGHS build deps (cmake, maybe clang) to CI.

Depends on the candidate-comparison issue landing first.

Part of #753.

🤖 Generated with Claude Code

Activity

  1. milindsrivastava1997
    self-assigned this
    on Oct 4, 2026
  2. milindsrivastava1997
    added
    enhancementNew feature or request
    asap-planner
    on Oct 4, 2026

  3. milindsrivastava1997 commented on Oct 4, 2026

    @milindsrivastava1997
    milindsrivastava1997
    on Oct 4, 2026
    ContributorAuthor

    Intended candidate workflow and boundaries

    The optimizer pipeline is:

    1. Extract optimizer items. Items deduplicate only RQE occurrences with identical AQE requirements, repeat interval T, accuracy_sla, and latency_sla; their query_frequency_hz is count * 1000 / T_ms.
    2. Enumerate every self-consistent candidate for each item. Optimizer: assignment unit = (AQE, repeat interval, accuracy_sla, latency_sla) #755 + Optimizer: window compatibility = lookback%W, T%S, W%S per item #758 own this stage: generation uses the item\047s T and window compatibility is L % W == 0, T % S == 0, and W % S == 0 (tumbling: S = W).
    3. Union the per-item candidates into a workload-wide pool and deduplicate configs by structural deployment identity.
    4. Build feasible (item, config) assignment edges, including capability/window rules and the later SLA filters.
    5. Solve facility location: choose deployed configs and exactly one feasible config for each item. A deployed config may serve multiple items.
    6. Size retention for each shared deployment to the maximum required by its assignments (Retention: take max across shared aggregation refs; sliding depth (n-1)*W/S+1 #760).

    Boundary: #755 + #758 should retain the existing per-item enumerate_candidates API and test its output. The workload-wide candidate pool, config deduplication, feasibility edges, and deployment/assignment decisions belong in this issue\047s MILP implementation.

  4. milindsrivastava1997 commented on Oct 27, 2026

    @milindsrivastava1997
    milindsrivastava1997
    on Oct 27, 2026
    ContributorAuthor

    Superseded by the rqe-optimizer MILP path (#790, ProjectASAP/sketch-bench#129, #794); the greedy optimizer was removed in #807. No port: rqe-optimizer is used as a library.

  5. milindsrivastava1997
    closed this as not plannedon Oct 27, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

asap-plannerenhancementNew feature or request

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions