acceptodds
Under review as a conference paper at ICLR 2027

Towards Provably Robust Combinatorial Optimization Solvers: Certification and Enhancement

Abstract

Combinatorial optimization (CO) has received increasing attention from the machine learning (ML) community, often regarding accelerating the solving process or discovering heuristics beyond hand-craft. In this paper, we dive into another aspect for bridging ML to CO: certification of the solver's robustness, especially in a solver-agnostic manner. In fact, existing theoretically-grounded certification methods are mainly confined to classification problems, while the robustness of CO solvers has largely been evaluated empirically. We explore the certified robustness concept as well as robustness enhancement strategy for CO solvers. First, we introduce a general definition of certified robustness for CO solvers, and extend the randomized smoothing, a well-established robustness certification technique originally designed for categorical classifiers. Using the objective value attained by the solver as the robustness evaluation metric, we provide theoretical guarantees that bound, in 1-Wasserstein distance, the variation between the corresponding smoothed cumulative distribution functions (CDFs) under bounded perturbations to problem instances. Beyond certification, we leverage the local-instance perspective underlying smoothing and observe that some nearby instances can yield solutions that remain feasible for the given instance while attaining lower objective values on it. Based on this observation, a training-free robustness enhancement method is devised by searching for such easy instances and using their solutions as feasible alternatives for the given instance, without modifying or retraining the solver. Experiments across four CO problems and 14 solvers demonstrate the applicability of the certification framework and the effectiveness of the enhancement method. With a small inference-time sampling budget, the enhancement method reduces the objective value on 48 of 56 attacked instances (85.7%).

Primary area:
optimization
Keywords:
Combinatorial optimization, Learning for optimization, Robustness cerification, Randomized smoothing

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_JkSwOpenReview ↗
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 mm and nn 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 mm and nn. (see weaknesses)
Reviewer_inhgOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a new method for sensitivity analysis of CO problems. The authors consider two versions of perturbed CO problems. In the first, constraints are randomly enabled/disabled with some probability β\beta, and in the second, continuous parameters are perturbed with random Gaussian noise. The authors consider the Wasserstein distance between two perturbed instances, one of which is a perturbation around the original parameters, and the other is a perturbation around a perturbation (I found this slightly confusing when I was reading the paper but I understand it now). The paper gives bounds on the Wasserstein distance between the objective values of these random instances. The paper also proposes a "robustness enhancement method" which repeatedly solves restricted versions of a CO problem to try to find better solutions.

Critical strengths

This paper is generally well-written and the explanation is fairly easy to follow.

The theoretical results all seem to be correct as written.

It is quite easy to understand the experiments.

Overall this paper was enjoyable to read.

Critical weaknesses

The following sentence in the abstract is a bit strange to me: "Beyond certification, we leverage the local-instance perspective underlying smoothing and observe that some nearby instances can yield solutions that remain feasible for the given instance while attaining lower objective values on it." Is this because a solver may not have returned the optimal value the first time? I think is a bit strange to say solutions "attain lower objective values on" the new instance because when I first read this it sounded to me like they improved the optimal solution which is clearly not possible. But this could just be personal phrasing taste.

I don't think Y\mathcal{Y} (used in (1)) is defined anywhere.

The notion of perturbation used in this paper is different to what most other works about perturbed CO problems use. A perturbation seems to mean "disabling some of the constraints" in a lot of this paper. This is not a major problem but maybe this paper could use some more explanation as to why exactly this model is studied.

There are a lot of functions stacked on top of each other in Theorem 3.1. Maybe some intuition about the shape of the function B (and therefore the bound) could be nice.

The approach using Wasserstein distance between smoothed objectives is interesting, but I am not sure how practical it is. If I was a regular user of CO solvers, and I had to assess how distant two CO problems were from each other, it is surely more useful for me to calculate a bound on how far the solutions are from one another, or the gap in objective value. The Wasserstein distance is very abstract and I am not sure how useful it is in telling me how much the problem has changed. The authors can try to address this.

The experiments in 4.1 all compare different versions of this same method, so it is hard to tell how tight the bounds are compared to existing methods for perturbation analysis.

The enhanced robustness method seems to use a lot of solver calls (ne=100n_e=100). It is not clear that this gives an improvement in overall computational budget - if I had put the computational budget which was used across those 100 solves into a single solve, could I have gotten the same/a better result?

I honestly don't really see a link between the robustness certification and the robustness enforcement method. The authors could explain this a bit more.

Questions for authors

I have posed suggestions for things the authors should address in the "weaknesses" box.

Reviewer_pZPGOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes a solver-agnostic framework for certifying and enhancing the robustness of combinatorial optimization (CO) solvers. It extends randomized smoothing to bound changes in the distributions of achieved objective values under binary and continuous instance perturbations using the 1-Wasserstein distance. Additionally, it introduces a training-free enhancement method that solves nearby modified instances and transfers feasible, lower-cost solutions back to the original instance. Experiments across four CO problems and 14 classical and learning-based solvers demonstrate the certification framework and report improved objective values on 50 of 56 adversarially perturbed configurations generated.

Critical strengths

Solver-agnostic robustness certification

The paper provides a theoretically grounded framework for assessing the robustness of both conventional and learning-based CO solvers without requiring access to their internal structure. Extending randomized smoothing to continuous-valued objective distributions and establishing Wasserstein-distance bounds under different perturbation models is a useful contribution toward more general robustness certification.

Broad experimental coverage and practical applicability

The framework is evaluated across four distinct CO problems and 14 solvers, including classical heuristics, optimization software, and learning-based methods. The proposed enhancement procedure is also simple to integrate with existing solvers, requires no retraining, and preserves feasibility while selecting solutions with non-increasing objective values. This makes it potentially useful as a general-purpose improvement strategy.

Critical weaknesses

Limited significance and applicability of the robustness guarantees

The proposed certificates bound changes in smoothed distributions of achieved objective values rather than the robustness of the original CO solver. In particular, increasing the smoothing strength can yield arbitrarily strong certificates without improving the underlying solver. Moreover, changes in objective values do not necessarily indicate solver instability, since even optimal solutions can have different costs when the problem instance changes. It is also unclear whether the considered perturbations always preserve valid CO instances, e.g., acyclicity in DAG scheduling or nonnegative distances in ATSP. Finally, the theoretical contribution appears closely related to existing randomized smoothing results for continuous-valued distributions, particularly [44], making the novelty of the derived guarantees difficult to assess.

Insufficient experimental evidence for the claimed robustness enhancement

The enhancement method essentially performs additional optimization by solving nearby instances and retaining the best feasible solution, which guarantees a non-increasing objective value by construction. However, no comparison against conventional multi-start or perturbation-based search methods with equivalent computational budgets is provided, despite requiring 10–100 additional solver evaluations. Furthermore, ROCO attacks are generated against the original solvers rather than the enhanced methods, leaving their robustness against adaptive attacks untested. Consequently, the reported improvements on 50 of 56 attacked configurations demonstrate improved solution quality but do not establish a specific advantage in adversarial robustness over conventional randomized search.

Corrections:

  • The ICLR guidelines state: "Citations within the text should [...] include the authors’ last names and year", while they are purely numeric in the submission
  • Ref. [34]: Is cited as "insatnet: The positive linear satisfiability neural networks. 2013.", the correct referece is pobably: "LinSATNet: The Positive Linear Satisfiability Neural Networks, ICML, 2023"
  • Ref. [12]: Was published at ICLR 2022
  • Ref. [6]: Journal name omitted
  • Lines 194-200: Not clear what structure the matrix has, total number of entries is n? Also, repeated sentence explaing when it is 0 or 1
Questions for authors

1. Interpretation and significance of the robustness certificates (clarification)

The proposed guarantees bound changes in smoothed objective-value distributions rather than the robustness of the original solver. In particular, choosing a binary smoothing probability of β=0.5\beta=0.5 yields a zero Wasserstein-distance bound independently of the solver's actual robustness. How should these certificates be interpreted in practice, and how can one distinguish genuinely robust solvers from those obtaining strong certificates primarily through smoothing? Furthermore, how do the theoretical contributions differ from existing distributional randomized-smoothing guarantees, particularly [44]?

2. Validity of perturbations and certification guarantees (clarification)

How does the framework ensure that sampled perturbations preserve valid CO instances? For example, modifying DAG edges can introduce cycles, while Gaussian perturbations can violate nonnegativity or metric assumptions in ATSP. Are invalid instances rejected, projected, or otherwise handled, and do the theoretical guarantees remain valid under these modifications? Additionally, how is the finite integration range [rmin⁡,rmax⁡][r_{\min},r_{\max}] chosen to ensure that the estimated certificates account for the full objective-value distribution?

3. Effectiveness of the robustness enhancement (additional evidence).

The enhancement method performs 10–100 additional solver evaluations and retains the best feasible solution, guaranteeing non-increasing objective values by construction. Could the authors compare against conventional multi-start or perturbation-based search methods under the same computational budget? Moreover, since ROCO attacks target the original solver rather than the enhanced procedure, could the authors clarify whether the improvement persists against an adaptive attacker targeting the enhanced solver itself? Such evidence would help establish whether the method provides a specific robustness advantage rather than simply benefiting from additional optimization effort.

4. How does the framework distinguish solver instability from changes in the underlying optimization problem? (clarification)

The ATSP experiments perturb the objective coefficients rather than the constraints, so even an exact solver can exhibit changes in achieved objective value. Would certifying changes in the optimality gap, rather than raw objective values, provide a more meaningful measure of solver robustness? Furthermore, how does the proposed constraint-tightening interpretation apply to ATSP, where increasing edge costs does not change the feasible set?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.