Solving Recurrent MIPs with Semi-supervised Graph Neural Networks
This addresses the need for faster re-optimization in domains like transportation and routing, where parameters change over time, but it is incremental as it builds on existing ML-based optimization methods.
The paper tackles the problem of automating and expediting the solution of Mixed-Integer Programs (MIPs) by predicting variable values, showing gains over other ML-based optimization approaches in experiments with binary MIPs.
We propose an ML-based model that automates and expedites the solution of MIPs by predicting the values of variables. Our approach is motivated by the observation that many problem instances share salient features and solution structures since they differ only in few (time-varying) parameters. Examples include transportation and routing problems where decisions need to be re-optimized whenever commodity volumes or link costs change. Our method is the first to exploit the sequential nature of the instances being solved periodically, and can be trained with ``unlabeled'' instances, when exact solutions are unavailable, in a semi-supervised setting. Also, we provide a principled way of transforming the probabilistic predictions into integral solutions. Using a battery of experiments with representative binary MIPs, we show the gains of our model over other ML-based optimization approaches.