Skip to content

Add a size budget to concrete path execution #1178

Description

@isPANN

Summary

Running candidate paths on an instance has no size or time limit. Some reductions produce huge targets from small inputs, and pred path <src> <dst> <instance> then hangs or runs out of memory. This is the local, reproducible form of #1152 (timeouts when MIPLIB instances are reduced toward a solver).

In a sweep of all variants' canonical examples (--limit 20), 8 runs timed out after 30 s and 1 was killed (probably out of memory). Timing individual prefixes (pred reduce --via):

Step Input bundle Output
MinimumCoveringByCliques → ILP 41 KB 600 MB
TravelingSalesman → ILP 21 KB 13 MB, then ILP → QUBO > 20 s
LongestCommonSubsequence → MIS ~1 KB example 61 MB
MinimumSetCovering → ILP (from the LCS→MIS output) 37 MB > 20 s
MVC → LCS → MIS (from a SAT example) 35 KB > 20 s

execute_paths also keeps every shared prefix's intermediate problem in memory until the whole batch finishes.

Proposal

  • Add a size budget to instance execution (for example a maximum on the target's parameters or on total variables and constraints), checked after every step. Stop a path that exceeds it and report it as stopped over budget, alongside executed and failed.
  • Where a step's symbolic contract is exact, or an upper_bound that is already within budget, use it to decide before building the target. That needs parameters to be available (Make reduction size formulas available end-to-end (ILP → QUBO first) #1175).
  • Free intermediate results once no remaining path needs that prefix.
  • Expose the budget in the CLI and MCP with a sane default.
  • Tests with a deliberately blowing-up path, kept under the 5 s test limit.

Depends on: #1177 (per-path failure isolation) and #1175 (available size formulas, for the pre-build check). Feeds into #1179 (path ranking).

Activity

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

    enhancementNew feature or request

    Type

    No type

    Projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions