A Hybrid Reinforcement and Self-Supervised Learning Aided Benders Decomposition Algorithm

A team of researchers from the University of Minnesota (Bernard T. Agyeman, Zhe Li, Ilias Mitrai, Prodromos Daoutidis) has introduced a hybrid machine learning framework to accelerate generalized Benders decomposition (GBD), a classic algorithm for solving mixed-integer nonlinear programming (MINLP) problems. The approach combines a graph-based reinforcement learning (RL) agent with a self-supervised neural network. The RL agent operates on a bipartite graph representation of the master problem, determining integer variable assignments through a verification mechanism. These assignments then feed into a KKT-informed neural network, trained via self-supervision to predict primal-dual solutions that approximately satisfy the Karush-Kuhn-Tucker (KKT) conditions of the subproblem. The predicted solutions are used to directly construct Benders cuts, bypassing the need for expensive subproblem solves.

The framework was evaluated on a MINLP case study, achieving a 57.5% reduction in solution time compared to classical GBD while consistently recovering optimal solutions across all test instances. This work, published on arXiv (2604.22107), demonstrates how reinforcement learning and neural networks can significantly enhance traditional optimization algorithms, particularly for complex systems where computational efficiency is critical. By replacing iterative subproblem solves with learned predictions, the method offers a practical path to faster decision-making in engineering, operations research, and other fields reliant on large-scale optimization.