- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper adapts randomized smoothing, which is used for image classification, to CO, providing provable and solver-agnostic certified robustness guarantees. It also proposes a training-free enhancement method that adds new constraints or tightens the original constraints, samples solutions, and outputs the one that achieves the lowest cost on the original instance. Claims are validated through 4 CO problems, 14 solvers, and 56 attack scenarios.
Critical strengths
The topic itself, robustness of CO solvers to instance perturbations, is interesting and meaningful, and the certification and enhancement discussed in the paper are solver-agnostic, which provides broad applicability.
Critical weaknesses
- Datasets and solvers. This paper claims the certification and enhancement are solver-agnostic. However, the list of solvers included in the experiments could be more comprehensive, especially learning-based solvers. I understand that some open-source implementations only support certain CO problems, but the claims can be strengthened by adding different additional solvers to each CO problem in the experiments. It is noted in the manuscript that ML4CO-Bench-101 was used. There are other solvers implemented that could be incorporated. Additionally, it is claimed in the manuscript that multiple datasets were used for each problem, but the main text only shows results on one dataset for each problem, and the appendix only shows one solver for the remaining datasets. The limitations of datasets and solvers leave the practical generality of the methods insufficiently demonstrated.
- Runtime. The enhancement strategy introduces overhead, but no runtime was reported. The analysis of the tradeoff between solution quality and computational overhead with respect to different and is not presented.
Questions for authors
- Could the authors provide results on more learning-based solvers and all datasets mentioned in the text (see weaknesses)?
- Could the authors provide the runtime of the enhancement step? How does it compare to the runtime of the inference time of the solvers without any enhancement? It would be interesting to see if there is any relationship between the solution quality and the computational overhead with respect to different and . (see weaknesses)