A learning-based algorithm to quickly compute good primal solutions for Stochastic Integer Programs
This addresses the computational challenge of solving stochastic integer programs for operations research and optimization practitioners, though it is incremental as it builds on existing scenario-based methods with a learning twist.
The paper tackles the problem of quickly computing near-optimal primal solutions for two-stage stochastic integer programs by proposing a learning-based algorithm that predicts a representative scenario to ensure feasibility and near-optimality, achieving competitive computing times with general-purpose solvers.
We propose a novel approach using supervised learning to obtain near-optimal primal solutions for two-stage stochastic integer programming (2SIP) problems with constraints in the first and second stages. The goal of the algorithm is to predict a "representative scenario" (RS) for the problem such that, deterministically solving the 2SIP with the random realization equal to the RS, gives a near-optimal solution to the original 2SIP. Predicting an RS, instead of directly predicting a solution ensures first-stage feasibility of the solution. If the problem is known to have complete recourse, second-stage feasibility is also guaranteed. For computational testing, we learn to find an RS for a two-stage stochastic facility location problem with integer variables and linear constraints in both stages and consistently provide near-optimal solutions. Our computing times are very competitive with those of general-purpose integer programming solvers to achieve a similar solution quality.