Learning Fast Optimizers for Contextual Stochastic Integer Programs

Abstract

We present a novel RL-based approach to learning a fast and highly scalable solver for a two-stage stochastic integer program in the large-scale data setting. Branch and bound solvers such as SCIP do not scale to large datasets for this problem class. Additionally, they solve each instance independently, without any knowledge transfer across instances. We address these limitations with a learnable local search solver that jointly learns two policies, one to generate an initial solution and another to iteratively improve it with local moves. The policies use contextual features for a problem instance as input, which enables learning across instances and generalization to new ones. We also propose learning a policy to estimate a bound on the objective using dual decomposition. Benchmark results show that on test instances our approach rapidly achieves approximately 30% to 2000% better objective value, which SCIP requires more than an order of magnitude more running time to match. Our approach also achieves better solution quality on seven out of eight benchmark problems than more scalable baselines such as Tabu Search and Progressive Hedging.