# Graph-Based Imitation and Reinforcement Learning for Efficient Benders Decomposition

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 22 of its 64 references that are in the map.
- First posted on arXiv 14 Nov 2025.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 22 of 22)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphs](https://mlsanity.com/paper/1704.02901/) (2017)
- [Uncertainty Quantification and Deep Ensembles](https://mlsanity.com/paper/2007.08792/) (2020)
- [Automated Algorithm Selection: Survey and Perspectives](https://mlsanity.com/paper/1811.11597/) (2018)
- [Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning](https://mlsanity.com/paper/2206.13414/) (2022)
- [Graph Neural Networks in TensorFlow and Keras with Spektral](https://mlsanity.com/paper/2006.12138/) (2020)
- [Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs](https://mlsanity.com/paper/2107.10201/) (2021)
- [Online Mixed-Integer Optimization in Milliseconds](https://mlsanity.com/paper/1907.02206/) (2019)
- [A Survey of Methods for Automated Algorithm Configuration](https://mlsanity.com/paper/2202.01651/) (2022)
- [Benders Cut Classification via Support Vector Machines for Solving Two-stage Stochastic Programs](https://mlsanity.com/paper/1906.05994/) (2019)
- [Fast Continuous and Integer L-shaped Heuristics Through Supervised Learning](https://mlsanity.com/paper/2205.00897/) (2022)
- [Computationally efficient solution of mixed integer model predictive control problems via machine learning aided Benders Decomposition](https://mlsanity.com/paper/2309.16508/) (2023)
- [Taking the human out of decomposition-based optimization via artificial intelligence: Part II. Learning to initialize](https://mlsanity.com/paper/2310.07082/) (2023)
- [Accelerating process control and optimization via machine learning: A review](https://mlsanity.com/paper/2412.18529/) (2024)
- [Learning to control inexact Benders decomposition via reinforcement learning](https://mlsanity.com/paper/2508.06700/) (2025)
- [Graph-Based Modeling and Simulation of Complex Systems](https://mlsanity.com/paper/1812.04983/) (2018)

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

- [Feasibility-Aware Imitation Learning for Benders Decomposition](https://mlsanity.com/paper/2604.04801/) (2026)
- [Atoms to Processes: The Role of Artificial Intelligence and Machine Learning in Chemical Engineering](https://mlsanity.com/paper/2610.02014/) (2026)

## Abstract (arXiv)

This work introduces an end-to-end graph-based agent for accelerating the computational efficiency of Benders Decomposition. The agent's policy is parameterized by a graph neural network which takes as input a bipartite graph representation of the master problem and proposes a candidate solution. The agent is trained using a two-stage approach that combines imitation (IL) and reinforcement learning (RL). IL is used to mimic a solver and obtain a warm-start policy which is then finetuned using RL with a reward signal that balances feasibility and computational efficiency. We augment the agent with a verification mechanism that checks the agent's prediction for feasibility and solution quality. The framework is evaluated in two case studies: (i) an illustrative mixed-integer nonlinear program, where it reduces the solution time by 42% without loss of solution quality, and (ii) a closed-loop irrigation scheduling problem, where it achieves a 23% time reduction without compromising water use efficiency.