Neur2SP: Neural Two-Stage Stochastic Programming
Stochastic programming is a powerful modeling framework for decision-making
under uncertainty. In this work, we tackle two-stage stochastic programs
(2SPs), the most widely applied and studied class of stochastic programming
models. Solving 2SPs exactly requires evaluation of an expected value function
that is computationally intractable. Additionally, having a mixed-integer
linear program (MIP) or a nonlinear program (NLP) in the second stage further
aggravates the problem difficulty. In such cases, solving them can be
prohibitively expensive even if specialized algorithms that exploit problem
structure are employed. Finding high-quality (first-stage) solutions -- without
leveraging problem structure -- can be crucial in such settings. We develop
Neur2SP, a new method that approximates the expected value function via a
neural network to obtain a surrogate model that can be solved more efficiently
than the traditional extensive formulation approach. Moreover, Neur2SP makes no
assumptions about the problem structure, in particular about the second-stage
problem, and can be implemented using an off-the-shelf solver and open-source
libraries. Our extensive computational experiments on benchmark 2SP datasets
from four problem classes with different structures (containing MIP and NLP
second-stage problems) show the efficiency (time) and efficacy (solution
quality) of Neur2SP. Specifically, the proposed method takes less than 1.66
seconds across all problems, achieving high-quality solutions even as the
number of scenarios increases, an ideal property that is difficult to have for
traditional 2SP solution techniques. Namely, the most generic baseline method
typically requires minutes to hours to find solutions of comparable quality.