REVIEW 3 major objections 4 minor 5 references
Algorithms the min-max regret 0-1 Integer Linear Programming Problem with Interval Data
T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict Short empirical note on two known heuristics for interval min-max regret 0-1 ILP; useful as a pointer but the statistical conclusion overreaches. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (3)
- [Section 3, final paragraph] 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 3, Table 1 and surrounding text] 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 3, statistical reporting] 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.
minor comments (4)
- [Title and Abstract] 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 1] 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 2.2] 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 3, Table 1] 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.
Circularity Check
No circularity: the comparison is empirical and self-contained.
full rationale
The paper's derivation chain is: define MMR-ILP using the standard worst-case scenario characterization cited from an external survey; apply two published metaheuristics (AMU and SBA); run them on MIPLIB-derived instances; compare their running times and relative deviations against the same Benders-like upper bound; and test the deviation difference with Wilcoxon. None of the reported outputs is a fitted parameter renamed as a prediction, and no input quantity is defined in terms of a quantity it is later claimed to explain. The statement that SBA considers the mean and upper scenarios and therefore produces solutions at least as good as AMU follows directly from the definitions in Sections 2.1 and 2.2, not from a self-referential construction. The self-citations to Carvalho et al. and Coco et al. are used only for instance generation and SBA parameter settings; they are experimental provenance, not load-bearing assumptions that force the AMU-versus-SBA conclusion. The weak point of the paper is statistical: interpreting p > 0.05 as evidence that the two deviations are equal, and using an upper bound instead of an optimality certificate. That is a validity and correctness concern, but it is not circularity.
Assumptions & free parameters
free parameters (1)
- SBA scenario parameters alpha, beta, gamma =
alpha=0.5, beta=1.0, gamma=0.05
assumptions (3)
- domain assumption The worst-case scenario for a solution x is the scenario where each coefficient equals its upper bound if x_i=1 and its lower bound if x_i=0 (cited from [1]).
- domain assumption AMU is a 2-approximation algorithm for interval-data min-max regret problems (cited from [4]).
- domain assumption The commercial solver CPLEX correctly solves the ILP subproblems produced at each scenario.
Cite this review
Pith. "Pith review of Algorithms the min-max regret 0-1 Integer Linear Programming Problem with Interval Data." pith.science (2026). https://pith.science/paper/5RPKAT2C
@misc{pith2026190805082,
author = {Pith},
title = {Pith review of: Algorithms the min-max regret 0-1 Integer Linear Programming Problem with Interval Data},
year = {2026},
howpublished = {\url{https://pith.science/paper/5RPKAT2C}},
note = {Machine review of arXiv:1908.05082}
}
read the original abstract
We address the Interval Data Min-Max Regret 0-1 Integer Linear Programming problem (MMR-ILP), a variant of the 0-1 Integer Linear Programming problem where the objective function coefficients are uncertain. We solve MMR-ILP using a Benders-like Decomposition Algorithm and two metaheuristics for min-max regret problems with interval data. Computational experiments developed on variations of MIPLIB instances show that the heuristics obtain good results in a reasonable computational time when compared to the Benders-like Decomposition algorithm.
Reference graph
Works this paper leans on
- [1]
-
[2]
A scenario based heuristic for the robust shortest path tree problem
Iago A Carvalho, Thiago F Noronha, Christophe Duhamel, a nd Luiz FM Vieira. A scenario based heuristic for the robust shortest path tree problem. IF AC-PapersOnLine, 49(12):443–448, 2016
work page 2016
-
[3]
Senario-based heuristics with path-relinking for the robust set covering problem
Amadeu A Coco, Andr´ ea Cynthia Santos, and Thiago F Noron ha. Senario-based heuristics with path-relinking for the robust set covering problem. In Proceedings of the XI Metaheuristics Interna- tional Conference (MIC), 2015
work page 2015
-
[4]
An approximation a lgorithm for interval data minmax regret combinatorial optimization problems
Adam Kasperski and Paweł Zieli´ nski. An approximation a lgorithm for interval data minmax regret combinatorial optimization problems. Information Processing Letters, 97(5):177–180, 2006
work page 2006
-
[5]
The robu st shortest path problem with interval data via benders decomposition
Roberto Montemanni and Luca Maria Gambardella. The robu st shortest path problem with interval data via benders decomposition. 4OR: A Quarterly Journal of Operations Research , 3(4):315–328, 2005. Cartagena, July 28-31, 2019
work page 2005
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.