Research map / Graph learning / Graph algorithms and clustering
Towards General Algorithm Discovery for Combinatorial Optimization: Learning Symbolic Branching Policy from Bipartite Graph
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GS4CO, which generates interpretable symbolic variable-selection branching policies directly from bipartite graph inputs using a Transformer with tree-structural encodings trained via PPO with a risk-seeking objective, and shows these lightweight policies beat human-designed and learned baselines on CPU-based SCIP.
Problem
Learned branching policies for exact MILP/combinatorial optimization solvers are black-box neural networks, and existing symbolic distillation from GNNs accumulates error and needs hand-crafted features, limiting interpretability and generality.
Approach
Represent symbolic branching policies directly over variable-constraint bipartite graph features with unified symbolic aggregation subtrees, and generate them end-to-end with a decoder-only Transformer augmented with positional, layer, active parent/sibling, and spatial tree encodings, optimized by PPO on imitation accuracy against full strong branching, instead of layer-wise distillation from GNN
Key results
- On Easy Setcover, GS4CO solves in 13.29s with 24/50 wins vs. 13.88s for Hybrid (18/50) and 18.12s for RPB, the best CPU-only baseline.
- GS4CO policies are about 500x smaller than GNNs (0.49 KB vs 266 KB) and about 20x faster to infer on CPU (1.84 ms vs 33.88 ms) on Setcover.
- Imitation accuracy on Setcover reaches 44.13% for GS4CO vs. 54.18% for GNN and 37.28% for Distilling-GNN.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use GS4CO instead of the strongest CPU baseline | branching policy · Indset Easy, Medium, and Hard | time (s): 54.60 -> 53.18; 309.91 -> 217.67; 2223.04 -> 2157.23 | Helped |
| use GS4CO instead of the strongest CPU baseline | branching policy · Cauctions Easy, Medium, and Hard | time (s): 3.35 -> 3.16; 33.12 -> 30.58; 351.75 -> 326.19 | Helped |
| use GS4CO instead of the strongest CPU baseline | branching policy · Setcover Easy, Medium, and Hard | time (s): 13.88 -> 13.29; 105.13 -> 103.74; 2160.35 -> 2100.53 | Helped |
| use GS4CO instead of the strongest CPU baseline | branching policy · Facilities Easy, Medium, and Hard | time (s): 71.11 -> 76.27; 284.24 -> 295.82; 1219.91 -> 1018.70 | Mixed |
| add end-to-end symbolic policy generation instead of iteratively distilling a trained GNN (ablation) | GS4CO · Setcover | accuracy (%): 37.28 -> 44.13 | Helped |
| add the Transformer sequential model instead of LSTM (ablation) | GS4CO · Setcover | accuracy (%): 40.05 -> 44.13 | Helped |
| add tree-structural encodings (ablation) | GS4CO · Setcover | accuracy (%): 35.73 -> 44.13 | Helped |
| add graph-input-specific constraints (ablation) | GS4CO · Setcover | accuracy (%): 41.85 -> 44.13 | Helped |
Surprising findings
- The learned symbolic policies are slightly less accurate than the prior hand-crafted symbolic policy Symb4CO, which the authors attribute to lacking complex human-designed features.
- Distilling symbolic functions layer-by-layer from a trained GNN performs worse than the GNN-free end-to-end generation, which is the paper's motivating observation.
Limitations
- Requires manually designed graph node/constraint/edge features for each downstream task.
- Symbolic policies have an upper bound on accuracy and do not reach the complexity of expert branching rules like reliability pseudocost branching.
- Only the variable-selection component of branching is studied; other solver components are not addressed.
Experimental setup
Datasets: Setcover Cauctions Facilities Indset
Benchmarks: Setcover Cauctions Facilities Indset
Metrics: 1-shifted geometric mean solving time B&B nodes wins imitation accuracy model size inference time
Baselines: FSB RPB Trees GNN Hybrid Distilling-GNN LSTM
Builds on: Symb4CO deep symbolic optimization Gasse et al. 2019 GNN branching Cranmer et al. 2020 symbolic GNN distillation Graphormer
Closest papers by meaning
- Rethinking Branching on Exact Combinatorial Optimization Solver: The First Deep Symbolic Discovery Framework (ICLR 2024 · similarity 0.95)
- COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems (AAAI 2024 · similarity 0.88)
- GOAL: A Generalist Combinatorial Optimization Agent Learner (ICLR 2025 · similarity 0.88)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.87)
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.87)
- $\texttt{STRCMP}$: Integrating Graph Structural Priors with Language Models for Combinatorial Optimization (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.