mlsanityData to 14 Oct 2026

Graph-Based Imitation and Reinforcement Learning for Efficient Benders Decomposition

arXiv 2511.11870 ↗First posted 14 Nov 2025math.OCcited by 2

On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization

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.

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.

Builds on

22 of 64 references.

Closest ancestors · 1

Same direction, newest first

  1. 2025Learning to control inexact Benders decomposition via reinforcement learning8 Aug

Other references · 21

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  3. 2016Geometric deep learning: going beyond Euclidean datacited by 1,048
  4. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  5. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  6. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  7. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 318
  8. 2017Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphscited by 310
  9. 2020Uncertainty Quantification and Deep Ensemblescited by 139
  10. 2018Automated Algorithm Selection: Survey and Perspectivescited by 114
  11. 2022Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learningcited by 61
  12. 2020Graph Neural Networks in TensorFlow and Keras with Spektralcited by 60
9 more
  1. 2021Learning a Large Neighborhood Search Algorithm for Mixed Integer Programscited by 43
  2. 2019Online Mixed-Integer Optimization in Millisecondscited by 38
  3. 2022A Survey of Methods for Automated Algorithm Configurationcited by 30
  4. 2019Benders Cut Classification via Support Vector Machines for Solving Two-stage Stochastic Programscited by 9
  5. 2022Fast Continuous and Integer L-shaped Heuristics Through Supervised Learningcited by 6
  6. 2023Computationally efficient solution of mixed integer model predictive control problems via machine learning aided Benders Decompositioncited by 6
  7. 2023Taking the human out of decomposition-based optimization via artificial intelligence: Part II. Learning to initializecited by 5
  8. 2024Accelerating process control and optimization via machine learning: A reviewcited by 5
  9. 2018Graph-Based Modeling and Simulation of Complex Systemscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Feasibility-Aware Imitation Learning for Benders Decompositioncited by 0
  2. 2026Atoms to Processes: The Role of Artificial Intelligence and Machine Learning in Chemical Engineeringcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026A Hybrid Reinforcement and Self-Supervised Learning Aided Benders Decomposition Algorithm
  2. 2026Learning to Cut: Reinforcement Learning for Benders Decomposition
  3. 2025Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning
  4. 2021Solving Graph-based Public Good Games with Tree Search and Imitation Learning
  5. 2022Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories
  6. 2024Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective
  7. 2018Accelerating Imitation Learning with Predictive Models
  8. 2022Travel the Same Path: A Novel TSP Solving Strategy