{"id":"bf799a52-4b29-4e9a-b3de-47c861156d5e","arxiv_id":"1908.05082","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"On tested MIPLIB-derived instances, the simple Mean Upper heuristic is as accurate as the Scenario-Based Algorithm but about ten times faster, making it the preferred choice for interval-data 0-1 integer programming.","lead":"This paper applies two existing quick algorithms to optimization problems where costs are uncertain ranges, and compares them against a slower reference method. It reports that the simpler algorithm is much faster and produces solutions of similar quality to the more complex one.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The AMU-vs-SBA conclusion rests on treating a non-significant Wilcoxon result as evidence of equal quality, despite SBA's theoretical dominance; a one-sided test is needed.","rationale":"The reader's weakest_assumption concerns the BLD baseline: if the Benders-like decomposition bound is not close to optimal, the reported 9-10% deviations do not measure true optimality gaps, undermining the abstract's claim that the heuristics obtain 'good results.' That concern is valid and should remain part of the conditional verdict. However, it does not directly threaten the strongest claim that AMU performs better than SBA, because both heuristics are evaluated against the same per-instance BLD value, so the AMU-vs-SBA quality comparison is still meaningful even if BLD is loose. The more direct load-bearing weakness for that claim is statistical: the paper uses p > 0.05 from a Wilcoxon test as evidence that AMU and SBA have comparable solution quality, while the paper itself proves SBA's robustness cost is at most AMU's (Section 2.2). Failure to reject a two-sided null does not establish equivalence, especially with unknown sample size and high variance in the AMU column. A one-sided test or confidence interval on paired differences would settle whether the quality difference is real. Since the concern is about missing statistical evidence rather than a demonstrated contradiction, the CONDITIONAL verdict is appropriate; additional data and the one-sided test should be required before the empirical claim is accepted.","tokens_in":3353,"tokens_out":6864,"duration_ms":72111,"concrete_test":"Obtain the per-instance paired relative deviations (AMU and SBA against BLD) that produced Table 1, and run a one-sided Wilcoxon signed-rank test with alternative 'SBA deviation < AMU deviation', reporting n, the test statistic, and a 95% confidence interval for the median paired difference. Because Section 2.2 guarantees SBA's robustness cost is no worse than AMU's, a significant one-sided result would refute the 'no quality difference' premise and reverse the recommendation; a non-significant one-sided result with an upper confidence bound below the time advantage would support AMU.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3's final paragraph concludes 'AMU performs better than SBA ... since it has a smaller average running time and their relative deviation do not significantly differ.' The load-bearing step is the inference from p > 0.05 to 'deviations do not significantly differ' being interpreted as comparable quality. This is invalid as an equivalence claim, and the paper's own theory undermines it: Section 2.2 states SBA considers both the mean and upper scenarios, so SBA's returned solution has robustness cost at most that of AMU on every instance. The reported averages (SBA 9.00% vs AMU 10.39%) are in the direction predicted by this guarantee. A two-sided Wilcoxon test with p > 0.05 only shows failure to detect a difference; with unknown and probably small n (AMU std 22.16 suggests a few outliers), the test is underpowered. The conclusion should be that no quality difference was detected, not that AMU is preferable; if the one-sided hypothesis 'SBA deviations are smaller' were tested on paired data, even a few strict improvements could make it significant, reversing the practical recommendation.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses the Interval Data Min-Max Regret 0-1 Integer Linear Programming problem (MMR-ILP), in which objective coefficients are uncertain and each variable's coefficient lies in a known interval. The authors describe a Benders-like decomposition algorithm (BDA, inconsistently labeled BLD in Table 1) and adapt two existing metaheuristics, Algorithm Mean Upper (AMU) and Scenario-Based Algorithm (SBA), to MMR-ILP. They report computational experiments on variations of MIPLIB instances, comparing AMU and SBA against the BDA upper bound. The central conclusion, stated in the final paragraph of Section 3, is that AMU performs better than SBA because it has a smaller average running time while the relative deviations of the two heuristics do not significantly differ according to a Wilcoxon signed-rank test.","tokens_in":3514,"tokens_out":3344,"duration_ms":35309,"significance":"If the main conclusion were properly supported, the paper would offer useful practical guidance: a fast 2-approximation heuristic (AMU) that is competitive in solution quality with the more expensive scenario-based heuristic (SBA) would be attractive for large MMR-ILP instances. The paper also usefully recalls standard results: the worst-case scenario characterization of regret, the exponential-size formulation, and the 2-approximation guarantees of the two heuristics. However, the central empirical claim is not established by the reported evidence. The statistical inference from a non-significant two-sided Wilcoxon test to equivalence of solution quality is invalid, especially because the paper itself states that SBA considers both the mean and upper scenarios and therefore produces solutions at least as good as AMU. In addition, the BDA baseline is not validated with lower bounds or optimality certificates, so the reported relative deviations are not shown to measure true optimality gaps. The significance of the paper therefore rests on a load-bearing empirical argument that needs substantial additional support.","major_comments":[{"comment":"The conclusion that AMU performs better than SBA relies on interpreting a non-significant two-sided Wilcoxon test (p > 0.05) as evidence that the relative deviations of AMU and SBA are statistically equivalent. This inference is invalid: a non-significant result only indicates that the test failed to detect a difference, and with a small sample and an AMU standard deviation of 22.16%, the test is likely underpowered. Moreover, the paper's own Section 2.2 states that SBA considers both the mean and upper scenarios and therefore produces solutions at least as good as AMU, so the observed averages (SBA 9.00% vs. AMU 10.39%) are in exactly the direction predicted by SBA's theoretical dominance. The appropriate analysis would be a one-sided paired test for whether SBA deviations are smaller, or an explicit equivalence test with a pre-specified tolerance, rather than a two-sided test whose null hypothesis is the absence of any difference. As written, the central claim is unsupported.","section":"Section 3, final paragraph"},{"comment":"The Benders-like decomposition algorithm (BDA, referred to as BLD in Table 1) is used as the baseline for computing relative deviations, but no lower bounds or optimality certificates are reported. The text calls the quantity a 'primal bound,' which is an upper bound on the optimal value; if BDA is an exact algorithm, the paper should report that it terminates with a certificate of optimality and state the resulting gaps. Without this information, the reported AMU and SBA deviations of 10.39% and 9.00% cannot be interpreted as optimality gaps, and the claim that the heuristics obtain 'good results' is not substantiated.","section":"Section 3, Table 1 and surrounding text"},{"comment":"The experimental evaluation reports only averages and standard deviations over the full instance set, with no number of instances, no instance-level results, and no Wilcoxon test statistic or exact p-value. The large standard deviation for AMU (22.16%) suggests that the deviation distribution is skewed or contains outliers, which further weakens any claim based on average running time and average deviation. A complete report should include the number of instances, per-instance deviations and running times, the paired one-sided test result, and ideally a confidence interval or equivalence bound for the difference in deviations. Without these details, the reader cannot assess whether the reported difference in running time (201 s vs. 1983 s) is accompanied by a practically insignificant difference in quality.","section":"Section 3, statistical reporting"}],"minor_comments":[{"comment":"The title is missing the preposition 'for' and should read 'Algorithms for the min-max regret 0-1 Integer Linear Programming Problem with Interval Data.' The abstract says 'This abstract deals with problems' but should say 'This paper deals with problems.'","section":"Title and Abstract"},{"comment":"There are several grammatical issues, including 'an mathematical formulation' and 'a new set of linear constrains.' The sentence 'There are infinitely many scenarios' is correct but the phrase 'the value of the coefficient ci is unknown' would be clearer as 'is not known exactly but is known to lie in the interval [li, ui].'","section":"Section 1"},{"comment":"The reference to 'Coco et al. [3]' has a typo in the bibliography: 'Senario-based heuristics' should be 'Scenario-based heuristics.' Also, 'paramete settings' should be 'parameter settings'.","section":"Section 2.2"},{"comment":"The table caption says 'it's standard deviation' but should be 'its standard deviation,' and the text 'standard deviation deviation' contains a duplicated word. The abbreviation 'BLD' is used without definition; the algorithm is introduced as 'BDA' (Benders-like Decomposition Algorithm), so the table and text should use a single consistent abbreviation.","section":"Section 3, Table 1"}],"recommendation":"major_revision","confidential_remarks":"The paper is a short conference contribution whose main claim is empirical. The core problem is not the absence of theory but the mismatch between the reported statistical analysis and the conclusion drawn from it. I would advise the editor that the manuscript is not acceptable in its current form, but the issues are correctable with additional experiments (instance-level results, one-sided tests, equivalence testing) and better documentation of the BDA baseline. I also note that the paper's own statement that SBA dominates AMU in solution quality, combined with the observed average deviations, suggests that the final recommendation may actually reverse once a one-sided test is applied."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a six-page workshop paper applying two existing heuristics — AMU and SBA — to a general interval-data min-max regret 0-1 ILP formulation. The formulation itself is standard and the worst-case scenario characterization is correctly quoted from Aissi et al. That part is fine. What's new is only the computational comparison on MIPLIB-derived instances: AMU looks about ten times faster than SBA, with similar average relative deviations against the Benders bound. If you need a quick benchmark number for this problem class, this is a usable pointer.\n\nThat said, the central conclusion is overstated. The authors use a two-sided Wilcoxon test that fails to reject equal quality, and then claim AMU 'performs better.' Absence of evidence is not evidence of absence, and the paper's own theory cuts against them: SBA inspects the mean and upper scenarios, so its output is always at least as good as AMU's on robustness cost. Their averages (SBA 9.00% vs AMU 10.39%) point in that direction. A one-sided paired test is the natural analysis, and with a handful of instances where SBA is strictly better it could easily reach significance, reversing the practical recommendation. The authors need to either run the one-sided test or provide a proper equivalence margin.\n\nOther soft spots are mostly missing evidence rather than contradiction. The BDA baseline is cited but not described, no lower bounds or optimality certificates are reported, and we don't see instance-level results or code. The standard deviations — AMU's deviation std is 22.16 against a mean of 10.39 — suggest a few outliers dominate the numbers. That makes the averages fragile. Also, the SBA parameters come from the authors' own prior work, which is fine, but it means the comparison is tuned to one algorithm's advantage, even if unintentionally.\n\nThe paper would be strengthened by releasing instances, code, and per-instance bounds. As it stands, it's a reasonable extended abstract but not a settle-able empirical claim. If I were editor, I'd send it to review because the question is practical and the flaws are fixable — but I'd insist on the one-sided test or an equivalence analysis, plus the missing baseline details, before accepting.\n\nThe citation pattern is honest: they cite Kasperski and Zielinski for AMU, Coco et al. and their own prior paper for SBA, and Aissi et al. for the scenario characterization. No red flags there.","headline":"Short empirical note on two known heuristics for interval min-max regret 0-1 ILP; useful as a pointer but the statistical conclusion overreaches.","tokens_in":4102,"tokens_out":1733,"would_cite":false,"duration_ms":15820,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C10","90C47","90C59"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper argues that, for 0-1 integer programs with interval-valued objective coefficients, solving just the mean and upper scenarios is enough to match an eleven-scenario search in regret quality while running far faster.","keywords":["min-max regret","interval data","0-1 integer linear programming","robust optimization","Benders-like decomposition","metaheuristics","approximation algorithm","benchmark instances"],"falsifier":"Solve the smallest benchmark instances to proven optimality, either by enumerating the robust min-max formulation with a commercial MIP solver or by computing lower bounds inside the decomposition, and compare the optimal regret values with AMU's outputs; if the true optimality gap is materially larger than the reported 9-10 percent relative deviation, the paper's conclusion that the heuristics give good results would be unsupported.","tokens_in":3113,"feed_emoji":"⏱️","tokens_out":10329,"duration_ms":92977,"temperature":0.7,"pith_summary":"The paper addresses a robust version of 0-1 integer linear programming in which each objective coefficient is only known to lie in an interval, and the goal is to minimize worst-case regret against the scenario-optimal solution. It compares an exact Benders-like decomposition with two heuristics: AMU, which solves only the mean scenario and the upper scenario, and SBA, which sweeps eleven scenarios between the lower and upper bounds. On modified standard benchmark instances, the two heuristics report nearly identical quality, around nine to ten percent above the decomposition upper bound, but AMU runs about ten times faster than SBA, roughly 200 seconds versus 2000 seconds, while the decomposition averages almost 5000 seconds. The paper concludes that AMU is the preferred practical method for these instances because its regret quality is not statistically different from SBA's and its running time is much smaller.","feed_headline":"Two-scenario heuristic outruns eleven-scenario rival","feed_subtitle":"On interval-data 0-1 ILPs, AMU matches SBA's regret quality in about a tenth of the time.","key_machinery":"The load-bearing object is the worst-case scenario $S_x$ of a solution $x$, defined by setting each objective coefficient to $u_i$ when $x_i=1$ and to $l_i$ otherwise. In that scenario the robust cost becomes $$Z(x) = \\sum_i u_i x_i - \\min_y \\sum_i (l_i + (u_i - l_i)x_i)y_i,$$ which reduces each regret evaluation to one standard 0-1 integer program. AMU exploits this by constructing only two candidate scenarios, the mean scenario and the upper scenario, computing the robust cost of each candidate, and returning the one with smaller regret; it inherits a 2-approximation guarantee from the earlier algorithm on which it is based. SBA samples target scenarios between the lower and upper scenarios, using parameters that produce eleven candidates, and therefore always sees at least the two scenarios that AMU sees. The Benders-like decomposition provides the upper bound against which both heuristics are compared in the experiments.","core_discovery":"The central claim is that the min-max regret version of 0-1 integer linear programming with interval data can be handled well in practice by a simple two-scenario heuristic. For any feasible solution $x$, the scenario that maximizes its regret is the one in which each selected variable contributes its upper coefficient and each unselected variable its lower coefficient; the paper uses the known consequence that the robust cost $Z(x)$ can be evaluated by solving one ordinary integer program. AMU solves the mean scenario and the upper scenario, evaluates the robust cost of both candidate solutions, and keeps the better one; SBA generalizes this by inspecting a sweep of eleven scenarios. Experimental results on modified standard benchmark instances place both heuristics about 9-10 percent above the Benders-like decomposition upper bound, with AMU averaging 201 seconds, SBA averaging 1983 seconds, and the decomposition averaging 4709 seconds; a nonparametric sign-rank test finds no significant difference between the heuristics' quality. The paper therefore asserts that AMU is the better algorithm for these instances, since it achieves the same regret quality in roughly a tenth of SBA's time.","pith_inferences":["The reported 9-10 percent deviations are measured against the Benders-like decomposition upper bound, not against proven optimal values; since no lower bounds or optimality certificates are reported, the true suboptimality of the heuristics could be larger than the table suggests.","If this behavior extends to other interval-data combinatorial problems whose deterministic version is an integer program, the two-scenario AMU could serve as a cheap default for robust knapsack, network design, and assignment variants.","A direct extension would be to warm-start the exact decomposition with AMU's mean-and-upper solution, potentially closing the regret gap much faster than starting from scratch."],"forward_implications":["On the tested class of interval-data 0-1 integer programs, a practitioner can replace an exact decomposition that averages about 4700 seconds with a roughly 200-second AMU run and accept a solution about ten percent above the decomposition upper bound.","The additional scenario evaluations in SBA do not pay off on these instances: its regret quality is statistically indistinguishable from AMU's even though it runs about ten times longer.","Because AMU carries a worst-case 2-approximation guarantee and shows about ten percent empirical deviation here, users get both a formal bound and a concrete expectation of behavior on similar instances.","Future heuristic comparisons for min-max regret integer programs can treat the two-scenario AMU as the time-quality benchmark rather than an eleven-scenario sweep."],"supporting_citations":[{"why":"Supplies the complexity argument that min-max regret inherits NP-hardness from the deterministic problem and the worst-case scenario characterization used to define robust cost.","marker":"[1]"},{"why":"Provides the interval-generation scheme for the benchmark instances and the scenario-based heuristic family to which SBA belongs.","marker":"[2]"},{"why":"Gives the scenario-sweep scheme and the parameter settings used by SBA in the experiments.","marker":"[3]"},{"why":"Establishes AMU as a 2-approximation algorithm and supplies the mean-scenario/upper-scenario selection logic.","marker":"[4]"},{"why":"Supplies the Benders-like decomposition used as the upper-bound baseline for the heuristic quality comparison.","marker":"[5]"}],"fun_headline_variants":["Two scenarios beat eleven: same regret, 10x faster","AMU heuristic: same robustness, tenth of the time","Interval-data ILP: two scenarios outrun eleven","Simple heuristic matches complex one, 10x faster","AMU: tenfold speedup, equal regret on ILPs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The comparison assumes the Benders-like decomposition upper bound is tight enough to be a meaningful baseline; if that bound is loose, the reported deviations do not actually show how far the heuristics are from optimal.","fun_headline_variants_meta":{"raw":{"variants":["Two scenarios beat eleven: same regret, 10x faster","AMU heuristic: same robustness, tenth of the time","Interval-data ILP: two scenarios outrun eleven","Simple heuristic matches complex one, 10x faster","AMU: tenfold speedup, equal regret on ILPs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000601,"raw_usage":{"total_tokens":2764,"prompt_tokens":858,"completion_tokens":1906,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":474,"completion_tokens_details":{"reasoning_tokens":1824}},"tokens_in":474,"tokens_out":1906,"duration_ms":12385,"temperature":1.0,"reasoning_tokens":1824,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:24:01.719247+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Solve the smallest benchmark instances to proven optimality, either by enumerating the robust min-max formulation with a commercial MIP solver or by computing lower bounds inside the decomposition, and compare the optimal regret values with AMU's outputs; if the true optimality gap is materially larger than the reported 9-10 percent relative deviation, the paper's conclusion that the heuristics give good results would be unsupported.","supporting_citations":[{"cited_title":"Aissi, C","cited_arxiv_id":null,"evidence_quote":"Supplies the complexity argument that min-max regret inherits NP-hardness from the deterministic problem and the worst-case scenario characterization used to define robust cost."},{"cited_title":"A scenario based heuristic for the robust shortest path tree problem","cited_arxiv_id":null,"evidence_quote":"Provides the interval-generation scheme for the benchmark instances and the scenario-based heuristic family to which SBA belongs."},{"cited_title":"Senario-based heuristics with path-relinking for the robust set covering problem","cited_arxiv_id":null,"evidence_quote":"Gives the scenario-sweep scheme and the parameter settings used by SBA in the experiments."},{"cited_title":"An approximation a lgorithm for interval data minmax regret combinatorial optimization problems","cited_arxiv_id":null,"evidence_quote":"Establishes AMU as a 2-approximation algorithm and supplies the mean-scenario/upper-scenario selection logic."},{"cited_title":"The robu st shortest path problem with interval data via benders decomposition","cited_arxiv_id":null,"evidence_quote":"Supplies the Benders-like decomposition used as the upper-bound baseline for the heuristic quality comparison."}],"review_version":1}