Towards Provably Robust Combinatorial Optimization Solvers: Certification and Enhancement

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%).