Research map / Learning theory and algorithms / Combinatorial and search optimization
DOGE-Train: Discrete Optimization on GPU with End-to-End Training
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.
Learns GNN-predicted parameters for a differentiable Lagrange decomposition (min-marginal averaging) dual solver on GPU, trained end-to-end with an unsupervised dual-objective loss, to solve LP relaxations of binary ILPs faster and better than FastDOG and Gurobi.
Problem
Solving LP relaxations of 0-1 integer linear programs quickly at large scale; existing ILP relaxation solvers are non-differentiable, sequential, and hard to improve with ML.
Approach
Make the GPU-parallel Lagrange decomposition / min-marginal averaging solver (FastDOG) differentiable via BDD-based backpropagation, generalize its damping and averaging parameters, and use a bipartite GNN to predict these parameters plus a non-parametric update that escapes fixed points, trained with an unsupervised dual-objective loss.
Key results
- On QAPLib, DOGE-M reaches g_I of 131 vs FastDOG's 276 and Gurobi's 3472, with a dual objective of 14.5e6 vs FastDOG's 5.7e6.
- On graph matching, DOGE-M achieves dual objective -4.8436e4 with g_I 0.2 vs FastDOG's -4.8912e4 at g_I 21 (FastDOG value is an outlier in the table).
- The learned GNN has only about 8k (DOGE) to 12k (DOGE-M) trainable parameters, trained on smaller instances and tested on much larger ones.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace FastDOG hand-designed updates with learned parametric and non-parametric updates | DOGE · Cell tracking | g_I: 18 -> 2.4 | Helped |
| replace FastDOG hand-designed updates with learned parametric and non-parametric updates | DOGE · Graph matching | g_I: 21 -> 0.3 | Helped |
| replace FastDOG hand-designed updates with learned parametric and non-parametric updates | DOGE · Independent set | g_I: 42 -> 0.3 | Helped |
| replace FastDOG hand-designed updates with learned parametric and non-parametric updates | DOGE · QAPLib | E (×10^6): 5.7 -> 12.1 | Helped |
| add LSTM recurrent connections | DOGE · QAPLib | g_I: 320 -> 131 | Helped |
| remove GNN message passing and use MLP predictors only (ablation) | DOGE · Graph matching | g_I: 0.19 -> 0.42 | Hurt |
| use one network instead of separate early- and late-stage networks (ablation) | DOGE · Graph matching | g_I: 0.19 -> 0.95 | Hurt |
| remove parametric update prediction (ablation) | DOGE · Graph matching | g_I: 0.19 -> 2.3 | Hurt |
| remove non-parametric update prediction (ablation) | DOGE · Graph matching | g_I: 0.19 -> 0.7 | Hurt |
| remove averaging-weight prediction (ablation) | DOGE · Graph matching | g_I: 0.33 -> 0.36 | Helped |
| remove damping-factor prediction (ablation) | DOGE · Graph matching | g_I: 0.33 -> 0.35 | Helped |
| add parametric update prediction (ablation) | FastDOG · Independent set | g_I: 14 -> 1.76 | Helped |
Surprising findings
- Learning only the non-parametric update or only the parametric update each already beats the non-learned FastDOG solver on graph matching.
Experimental setup
Datasets: Cell tracking (flywing tissue) Graph matching (3D nuclei) Independent set (random) QAPLib
Benchmarks: Cell tracking Graph matching Independent set QAPLib
Metrics: relative dual gap integral g_I dual objective E runtime t[s]
Baselines: Gurobi FastDOG dataset-specific solvers (fm-bca, cell tracking solver)
Builds on: FastDOG deferred min-marginal averaging binary decision diagrams
Closest papers by meaning
- On the Power of Small-size Graph Neural Networks for Linear Programming (NeurIPS 2024 · similarity 0.87)
- Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs (ICML 2025 · similarity 0.87)
- B$^3$-PWL: GPU-Batched Branch-and-Bound for Piecewise-Linear Optimization with SOS2 Constraints (NeurIPS 2026 · similarity 0.87)
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.86)
- Learning Sparse Approximate Inverse Preconditioners for Conjugate Gradient Solvers on GPUs (NeurIPS 2025 · similarity 0.86)
- StitchCUDA: An Automated Multi-Agents End-to-End GPU Programing Framework with Rubric-based Agentic Reinforcement Learning (ICML 2026 · similarity 0.86)
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.