- Rating
- 4
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
Given uncertain measurements over time, what is the fewest events that could explain them? The propsed idea finds a possible explanation. Under specific timing rules, perfectly measured checkpoints simplify the search. Computation then depends mainly on the longest stretch of uncertainty, making some otherwise difficult problems manageable.
Critical strengths
The method provides checkable mathematical evidence for its answers. The authors also clearly report unresolved cases and unsuccessful experiments. It resolves 666 of 672 retail queries, but those are small, constructed tasks. It is roughly 28% faster than exhaustive search on taxi tests, yet about as fast as another certifying optimization approach.
Critical weaknesses
The useful speed guarantee relies on restrictive assumptions: changes only increase the signal’s slope, and suitable exact checkpoints separate uncertain stretches. When every measurement is uncertain, the search can still become exponentially expensive.
Questions for authors
See above.
2 comments
Response to Reviewer i89x (part 2/2)
"666 of 672 … small, constructed tasks." The retail evidence is now complete, faithful to the model and large.
- All 672 retail queries are now decided: the solver-free evaluation settles the six that were open (Appendix V.4, Table 33).
- The log-derived queries are exact instances of the model. Integrated arrival counts satisfy constraints (1)–(3) exactly, with one jump per occupied ten-minute bin, and checkpoints (the observed values at bin boundaries) are released either exactly or as quantization cells, the interval obtained by rounding a value, as for low-precision telemetry (§6, Appendix I). Every window was fixed before solving.
- The evidence is large. From the same public log we certified exact minima for 128 new inputs with 12–96 labels (32 windows, four release regimes each, as in the submission; each in under 0.2 seconds) and for 48 inputs of 1, 7 and 28 days with up to 4,032 labels (each in under 5 seconds), against 6 labels in the submission (Appendix V.3, Table 32).
- Exact minima also show what standard tools get wrong: on 188 inputs, the relaxation (minimizing the total jump size) proposes more events than necessary on every input (median 1.8 times the minimum), and trend filtering (fitting a piecewise-linear signal with a penalty on the total slope change) returns a signal that no compatible trajectory realizes on 166 of them (Appendix V.7, Table 36).
"About as fast as another certifying optimization approach." Evaluated without an LP solver, Local DP is clearly faster than verified branch-and-bound, and the gap grows with the input. Already on the six-label taxi inputs of the submission, Local DP used slightly less CPU than the certifying MILP cascade and never needed the enumeration fallback, which the cascade needed 6 and 9 times (Table 8). The evidence (Appendix W; CPU seconds, separate runs on the same server):
- Faster on every query, and increasingly so. On 180 real-log and random inputs not built for this comparison, Local DP used less CPU than verified branch-and-bound (exact SCIP 10.1, whose rejections carry VIPR certificates, machine-checkable proofs of infeasibility) on all 349 queries both certified, with the same answers. The median ratio of SCIP's time to ours grows with the input, from 3.4 at 12 labels to 38 at 96 labels on retail windows, and from 6.4 at to 151 at on random inputs.
- It answers where verified branch-and-bound runs out of time. At and , SCIP certifies no infeasible budget within 600 seconds; our method needs under 0.6 seconds. On a panel built to stress the cheap bounds, SCIP needs 18–47 seconds to certify the infeasible budgets at and does not finish at within 600 seconds; our method needs under 0.1 seconds on both.
- One run answers every budget. One Local DP run returns the minimum, and with it the answer for every budget; a solver answers one budget per run.
- The two approaches also work together. On the downstream contracts, the MILP finds a sparse model and Local DP certifies that it is minimal.
- It is the same algorithm. The solver-free implementation reproduces all 3,406 certified facts of the submission's experiments (Appendix V.4).
In short, the two assumptions bound only the running time, never the exactness: the reset holds for jumps of either sign, random uncertainty keeps the uncertain stretches short with high probability, and even with no exact checkpoint the method answers exactly within seconds on inputs with thousands of labels. Evaluated without a solver, the method certifies both sides of the budget question, a witness when events suffice and an exact exclusion when they do not, at thousands of labels in seconds, and it used less CPU than verified branch-and-bound on every query that both certified.
We hope that our responses address all of your concerns, and we would be grateful if you would take them into account in your final assessment.
Response to Reviewer i89x (part 1/2)
Thank you for the accurate summary, and for valuing the checkable certificates and the complete reporting of unresolved cases; the revision keeps both. Neither assumption you name is needed for exact answers; they only bound the running time. The first can be dropped, and the second holds by itself, with high probability, when uncertainty falls at random rather than by design. Long uncertain stretches contain the NP-complete cases of the problem, and even there our method returns exact answers within seconds on inputs with thousands of labels. The retail evidence is now far larger, and once the algorithm is evaluated without a solver, it is faster than verified branch-and-bound on every query that both certify.
Notation: n is the number of labels (sampling intervals), and β is the length of the longest run of intervals that touch an uncertain observation; the cost of the algorithm is 2β times a polynomial. Local DP is our implementation of Algorithm 1; its solver-free implementation evaluates every step by exact polygon operations in rational arithmetic, without an LP solver (Appendices S and V).
Exact answers do not depend on either assumption. With the enlarged blocks of Corollary 11, Algorithm 1 returns the exact minimum, with a rational witness and an exact exclusion, on every input of the model. The two assumptions only bound its running time.
"Changes only increase the signal's slope." The reset does not need this.
"Suitable exact checkpoints separate uncertain stretches." Checkpoints need not be designed: random uncertainty keeps the uncertain stretches short, and long stretches cost far less in practice than in the worst case.
"When every measurement is uncertain, the search can still become exponentially expensive." Our bound confines the exponential cost to the uncertain stretches, and in practice exact answers come quickly even with no exact checkpoint at all (Appendix V.5, Table 34). Inputs in which every interval touches an uncertain observation are exactly those of the NP-completeness proof (Proposition 5), so no exact method, MILP and verified branch-and-bound included, is known to be efficient on all of them.