Skip to yearly menu bar Skip to main content


In-Person Poster presentation / poster accept

ROCO: A General Framework for Evaluating Robustness of Combinatorial Optimization Solvers on Graphs

Han Lu · Zenan Li · Runzhong Wang · Qibing Ren · Xijun Li · Mingxuan Yuan · Jia Zeng · Xiaokang Yang · Junchi Yan

MH1-2-3-4 #107

Keywords: [ combinatorial optimization ] [ graph neural networks ] [ robustness ] [ reinforcement learning ] [ Optimization ]


Abstract:

Solving combinatorial optimization (CO) on graphs has been attracting increasing interests from the machine learning community whereby data-driven approaches were recently devised to go beyond traditional manually-designated algorithms. In this paper, we study the robustness of a combinatorial solver as a blackbox regardless it is classic or learning-based though the latter can often be more interesting to the ML community. Specifically, we develop a practically feasible robustness metric for general CO solvers. A no-worse optimal cost guarantee is developed as such the optimal solutions are not required to achieve for solvers, and we tackle the non-differentiable challenge in input instance disturbance by resorting to black-box adversarial attack methods. Extensive experiments are conducted on 14 unique combinations of solvers and CO problems, and we demonstrate that the performance of state-of-the-art solvers like Gurobi can degenerate by over 20% under the given time limit bound on the hard instances discovered by our robustness metric, raising concerns about the robustness of combinatorial optimization solvers.

Chat is not available.