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
Depends on: #1177 (per-path failure isolation) and #1175 (available size formulas, for the pre-build check). Feeds into #1179 (path ranking).
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):execute_pathsalso keeps every shared prefix's intermediate problem in memory until the whole batch finishes.Proposal
stopped over budget, alongsideexecutedandfailed.exact, or anupper_boundthat 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).Depends on: #1177 (per-path failure isolation) and #1175 (available size formulas, for the pre-build check). Feeds into #1179 (path ranking).