# DOGE-Train: Discrete Optimization on GPU with End-to-end Training

arXiv: https://arxiv.org/abs/2205.11638 · HTML: https://mlsanity.com/paper/2205.11638/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 72 references that are in the map.
- First posted on arXiv 23 May 2022.

## Builds on (most cited first, 30 of 33)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning to learn by gradient descent by gradient descent](https://mlsanity.com/paper/1606.04474/) (2016)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [Algorithm Unrolling: Interpretable, Efficient Deep Learning for Signal and Image Processing](https://mlsanity.com/paper/1912.10557/) (2019)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Trainable Nonlinear Reaction Diffusion: A Flexible Framework for Fast and Effective Image Restoration](https://mlsanity.com/paper/1508.02848/) (2015)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem](https://mlsanity.com/paper/2110.07983/) (2021)
- [Hybrid Models for Learning to Branch](https://mlsanity.com/paper/2006.15212/) (2020)
- [Neural Graph Matching Network: Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching](https://mlsanity.com/paper/1911.11308/) (2019)
- [Differentiable Dynamic Programming for Structured Prediction and Attention](https://mlsanity.com/paper/1802.03676/) (2018)
- [Learning to Select Cuts for Efficient Mixed-Integer Programming](https://mlsanity.com/paper/2105.13645/) (2021)
- [Graph Neural Networks for Maximum Constraint Satisfaction](https://mlsanity.com/paper/1909.08387/) (2019)
- [Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers](https://mlsanity.com/paper/2011.06069/) (2020)
- [Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs](https://mlsanity.com/paper/2107.10201/) (2021)
- [Learning Large Neighborhood Search Policy for Integer Programming](https://mlsanity.com/paper/2111.03466/) (2021)
- [Adaptive Cut Selection in Mixed-Integer Linear Programming](https://mlsanity.com/paper/2202.10962/) (2022)
- [Fusion Moves for Graph Matching](https://mlsanity.com/paper/2101.12085/) (2021)
- [Improving Optimization Bounds using Machine Learning: Decision Diagrams meet Deep Reinforcement Learning](https://mlsanity.com/paper/1809.03359/) (2018)
- [MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models](https://mlsanity.com/paper/2004.08227/) (2020)
- [RAMA: A Rapid Multicut Algorithm on GPU](https://mlsanity.com/paper/2109.01838/) (2021)
- [Efficient Message Passing for 0-1 ILPs with Binary Decision Diagrams](https://mlsanity.com/paper/2009.00481/) (2020)
- [FastDOG: Fast Discrete Optimization on GPU](https://mlsanity.com/paper/2111.10270/) (2021)

## Built on by (most cited first, 6 of 6)

- [Learning Lagrangian Multipliers for the Travelling Salesman Problem](https://mlsanity.com/paper/2312.14836/) (2023)
- [Learning to Solve Combinatorial Optimization under Positive Linear Constraints via Non-Autoregressive Neural Networks](https://mlsanity.com/paper/2409.04495/) (2024)
- [Deep learning enhanced mixed integer optimization: Learning to reduce model dimensionality](https://mlsanity.com/paper/2401.09556/) (2024)
- [Predicting Accurate Lagrangian Multipliers for Mixed Integer Linear Programs](https://mlsanity.com/paper/2310.14659/) (2023)
- [Correlation Clustering of Organoid Images](https://mlsanity.com/paper/2403.13376/) (2024)
- [Scaling Decision-Focused Learning to Large Problems with Lagrangian Decomposition](https://mlsanity.com/paper/2606.08797/) (2026)

## Abstract (arXiv)

We present a fast, scalable, data-driven approach for solving relaxations of 0-1 integer linear programs. We use a combination of graph neural networks (GNN) and the Lagrange decomposition based algorithm FastDOG (Abbas and Swoboda 2022b). We make the latter differentiable for end-to-end training and use GNNs to predict its algorithmic parameters. This allows to retain the algorithm's theoretical properties including dual feasibility and guaranteed non-decrease in the lower bound while improving it via training. We overcome suboptimal fixed points of the basic solver by additional non-parametric GNN update steps maintaining dual feasibility. For training we use an unsupervised loss. We train on smaller problems and test on larger ones showing strong generalization performance with a GNN comprising only around 10k parameters. Our solver achieves significantly faster performance and better dual objectives than its non-learned version, achieving close to optimal objective values of LP relaxations of very large structured prediction problems and on selected combinatorial ones. In particular, we achieve better objective values than specialized approximate solvers for specific problem classes while retaining their efficiency. Our solver has better any-time performance over a large time period compared to a commercial solver. Code available at https://github.com/LPMP/BDD