Learning to reoptimize: a GNN-aided fix-and-optimize approach and an application to the Lot Sizing problem

In many operational contexts, solutions to NP-hard combinatorial optimization problems, modeled by means of Mixed-Integer Linear Programming (MILP), may become infeasible due to unpredictable disruptions. Typically, reoptimizing by solving the MILP formulation on the perturbed instance is not possible as new solutions must be obtained in a very short computing time, while simple repairing heuristics may result in low-quality solutions. To bridge this gap, we propose a learning-to-reoptimize framework, and apply it to the Lot Sizing Problem (LSP) under machine breakdown disruptions. We design a fix-and-optimize strategy aided by a Graph Neural Network (GNN) that efficiently computes a new solution within the neighborhood of a repaired solution. By representing the instance, the original solution and the disruption as a feature graph, we train a GNN to predict the likelihood that specific binary variables require to be modified. These predictions guide the selection of a small subset of variables to be reoptimized by an MILP solver, while the other variables are hard-fixed. Numerical experiments on a large dataset demonstrate that our approach handles effectively different problem sizes, and that it significantly outperforms a baseline alternative approach, yielding larger cost reductions within the same limited time budget.