Johannes Varga, Emil Karlsson, Guenther Raidl, Elina Rönnberg, Fredrik Lindsten, Tobias Rodemann, "Speeding up Logic-Based Benders Decomposition by Strengthening Cuts with Graph Neural Networks", 9th International Conference on Machine Learning, Optimization, and Data Science (LOD), 2023.

Logic-based Benders decomposition is a technique to solve optimization problems to optimality. It works by splitting the problem into a master problem, which neglects some aspects of the problem, and a subproblem, which adds cuts to the master problem to account for those aspects. These cuts need to be refi ned to achieve good overall performance. In this paper we investigate the use of Machine Learning to learn a good refi nement procedure. We apply Graph Neural Networks, as they have recently been successful in similar settings. Aim is to speed up the overall approach by reducing the number of iterations and by speeding up the cut refi nement procedure itself, compared to classical cut refinement procedures. We test the approach on a job scheduling problem with a single machine and multiple time windows per job and compare to approaches from the literature. Results show that our approach is very well capable in reducing the runtime to solve instances.