Towards General Algorithm Discovery for Combinatorial Optimization: Learning Symbolic Branching Policy from Bipartite Graph

Machine learning (ML) approaches have been successfully applied to accelerating exact combinatorial optimization (CO) solvers. However, many of them fail to explain what patterns they have learned that accelerate the CO algorithms due to the black-box nature of ML models like neural networks, and thus they prevent researchers from further understanding the tasks they are interested in. To tackle this problem, we propose the first graphbased algorithm discovery framework-namely, graph symbolic discovery for exact combinatorial optimization solver (GS4CO)-that learns interpretable branching policies directly from the general bipartite graph representation of CO problems. Specifically, we mainly focus on the variable selection part of the branching policy. We design a unified representation for symbolic variable selection policies with graph inputs, and then we employ a Transformer with multiple treestructural encodings to generate symbolic trees end-to-end, which effectively reduces the cumulative error from iteratively distilling graph neural networks. Experiments show that GS4CO learned interpretable and lightweight policies outperform all the baselines on CPU machines, including both the human-designed and the learning-based. GS4CO shows an encouraging step towards general algorithm discovery on modern CO solvers. Codes are available at https://github. com/MIRALab-USTC/L2O-GS4CO .