Neur2SP: Neural Two-Stage Stochastic Programming
Authors: Rahul Mihir Patel
Justin Dumouchelle
Elias Boutros Khalil
Merve Bodur
Venue: NeurIPS 2022 Accept (2022)

Abstract: 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 used class of stochastic programming models. Solving 2SPs exactly requires optimizing over an expected value function that is computationally intractable. Having a mixed-integer linear program (MIP) or a nonlinear program (NLP) in the second stage further aggravates the intractability, even when 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. Neur2SP makes no assumptions about the problem structure, in particular about the second-stage problem, and can be implemented using an off-the-shelf MIP solver. Our extensive computational experiments on four benchmark 2SP problem classes with different structures (containing MIP and NLP second-stage problems) demonstrate the efficiency (time) and efficacy (solution quality) of Neur2SP. In under 1.66 seconds, Neur2SP finds high-quality solutions across all problems 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.


Neur2SP: Neural Two-Stage Stochastic Programming
Justin Dumouchelle' Rahul Patel"
Elias B. Khalil
Merve Bodur
Department of Mechanical Industrial Engineering, University of Toronto
Abstract
Stochastic Programming is powerful modeling framework for decision-making under uncertainty. In this work, we tackle two-stage stochastic programs (2SPs), the most widely used class of stochastic programming models. Solving 2SPs exactly requires optimizing over an expected value function that computationally intractable. Having mixed-integer linear program (MIP) or nonlinear program (NLP) in the second stage further aggravates the intractability, ized 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 neural network obtain a surrogate model that can be solved more efficiently than the traditional extensive formulation approach. Neur makes no assumptions about the problem structure, particular about the second- stage problem, and can be implemented using an off-the-shelf MIP solver. Our extensive computational experiments on four benchmark 2SP problem classes with different structures (containing MIP and NLP second-stage problems) demonstrate the efficiency (time) and efficacy (solution quality) of Neur under 1.66 sec- onds, Neur finds high-quality solutions across all problems even the number scenarios increases, an ideal property that 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.
when special-
1 Introduction
Mathematical programming consists of gamut of tools to solve optimization problems. Under perfect information, i.e., when all the data deterministic and known, many these problems can be solved linear program (LP) or mixed-integer linear program (MIP). However, in many cases, there is need to deal with problems with partial information. Stochastic programming is one such framework that allows to incorporate uncertainty into decision-makinn
In this work, we focus our attention on Two-stage Stochastic Programs (2SPs). A 2SP involves two sets of decisions, namely the first-stage and second-stage (recourse) decisions, to be made before and after the uncertainty is realized, respectively. Given the (joint) probability distribution of the random parameters of the problem, the most common objective of 2SP is to optimize the expected value the decisions. For example, in a two-stage stochastic facility location problem, first-stage decisions consist of which facilities should be built whereas second-stage decisions involve assigning customers to open facilities to meet their stochastic demand, and the overall objective is to minimize the sum of the cost of the first-stage decisions and the expected cost of the second-stage decisions.
2SPs are usually solved via Sample Average Approximation (SAA), which limits the future un- certainty to a finite set of possible realizations (scenarios). The SAA approximation of a 2SP is
"These authors contributed equally. Corresponning author: shalil@mie utoronto.co ca.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Learning
Deployment
ReLU Neural Network (NN)
Flist-stage decsion
[[Fistisaage dectsion,
Expecied Seisand slage
swcent-aagg sakoa]]
okjacciiv value
Scaruno sor.
min c²xx + NN(x, scenario set)
Training [regression]
"MIPify" and solve
First-stage declsion
2SP
collection
unsean
scenario set
Overview of Neur2SP. The leftmost block is the input, namely, a 2SP. From the 2SP, follow the data generation procedure from Section 4.3 to obtain a dataset consisting of tuples of (first-stage decision, scenario set, corresponding expected second-stage objective value). We then train of the learning models presented in Section 4.1 1 to predict the expected cost given a first-stage decision and scenario set. The trained model is then embedded into a MIP using the procedure in Section 4.2 to obtain an approximate MIP (the "MIPify" step). Lastly, the approximate MIP is solved with an off-the-shelf MIP solver to obtain a first-stage 2SP solution.
Figure 1:
reduction to an equivalent deterministic problem and can be solved by the so-called extensive form: monolithic formulation where scenario copies of the second-stage decision variables are created and linked to the first-stage decisions. However, even for small 2SPs, solving the extensive form may be intractable as it requires introducing large number of (possibly integer) variables and (possibly nonlinear) constraints. As such, specialized algorithms are required. If the second-stage problem assumes the form of an LP, then algorithms such as Benders' decomposition (also known as the L-shaped method) can be leveraged efficiently solve the problem optimality. Unfortunately, in many practical applications of 2SP, the second-stage problem assumes the form of MIP, for which specialized decomposition algorithms might not be efficient. The existence of continuous first-stage variables linked to the second-stage problem significantly increases the difficulty of solving such problems. This exacerbated when the second-stage problem nonlinear, for which no general and atructure-agnostic solution strategy exists.
In this work, we propose Neur2SP, framework for constructing easier-to-soe surrogate op- timization problem for 2SP with the use of supervised deep learning. In a nutshell, a Rectified Linear Unit (ReLU) neural network is trained approximate the second-stage objective value for a set of scenarios. Using MIP-representable activation functions such as the ReLU, the forward computation of the trained network can be embedded into MIP. The surrogate problem is then confined to optimizing only first-stage decisions with respect to the first-stage objective function and the neural network approximation of the second-stage objective Assuming small and accurate neural network can be used, the surrogate problem is much smaller than the extensive form, and thus faster to solve. The entire procedure summarized in Figure Our main contributions are as follows:
Novelty: Neur2SP is the first generic machine learning approach for deriving a heuristic solution for 2SP. We introduce highly parallelizable data collection procedure and show two separate neural models which can be used to formulate a deterministic mixed-integer surrogate problem for 2SP;
2. Generality: Neur2SP can be used out-of-the -he- for 2SPs with linear and nonlinear objec- tives and constraints as well mixed-integer variables in both the first and second stages, all without using any problem structure, i.e., in purely data-driven way;
3. Performance:
Neur is shown to produce high-quality solutions significantly faster than the solely applicable general baseline method, the extensive form approach, for variety of benchmark problems, namely, stochastic facility location problem, an investment problem, server location problem, and pooling problem from chemical engineering.
Foor a fixed sirst-stage solution obtained via this surrogate, an optimal second-stage standd decision can be obtained relatively quickly for each scenario if desired.

---

2
Preliminaries
We introduce the 2SP setting and describe the MIP formulation for ReLU activation function which is central to the surrogate model we propose in this work. Appendix A summarizes the notation used.
2.1 Two-stage Stochastic Programming
A 2SP can be generally expressed minx [x] x E X), where R" is the first-stage cost vector, x E I" represents the first-stage decisions, A' is the first-stage feasible set, and & is the vector of random parameters that follow probability distribution IP with support E. The value function Q X' x E - IR returns the cost of optimal second-stage (recourse) decisions under realization given the first-stage decisions of x. In many cases, as the Q(x. E) is obtained by solving a mathematical program, evaluating the expected value function Eg fe(Q(x E) is intractable.
To provide more tractable formulation, the extensive form (EF) is used. Using set of K sce- narios, $1...., EKK, sampled from the probability distribution IP. EF
=\t minx m + Ek k= (xQ kk) x E X), where is the probability of scenario &. being realized. If Q(x,E) miny (F y (xx, {) then EF εx) can be expressed
K
min x.y
c Σ EIFFly: X Y. E Exx.
K
which can be solved through standard deterministic optimization techniques. However, the number of variables and constraints of the EF grows linearly with the number of scenarios. Furthermore, if Q(:.)) is the optimal value of a MIP or an nonlinear program (NIP), the EF model becomes significantly more challenging to solve as compared to the LP case, limiting its applicability even at small scale.
2.2 Embedding Neural Networks into MIPs
Mathematicallyy, an E-layer fully-connected neural network can be expressed h² aW bD); 1,....
: L 1; W + b Here, E Rm is the input, B E TR. is the prediction, h E Rdd is the i-th hidden layer, W E IR Rddxxd++1 is the matrix of weights from layer i to + 1, ba Rdd is the bias at the i-th layer, and a a non-linear activation function, here the activation function is given by ReLU(a) = (0, a} for E R.
hm++1= " m + b²*),
Central to Neur2SP is the embedding formulation proposed by [Fischetti and Jo, 2018]. For given hidden layer m, the j-th hidden unit, h7t can be written as
trained neural network into a MIP Here, we present the
dm
hTth = ReLU
Σ
W
14
+
63 pm-11
(1)
where wi is the element at the j-th row and i-th column of W and 67-11 is the j-th index of m To model ReLU a MIP for the j-th unit in the m-th layer, we use the variables hy, hy and hm for i ....., dm-1- 1. The ReLU activation is then modeled with the following constraints:
Am
m 11
+ 13 1m
mm
(2a)
1g
1=1
2) =1 + hy < 0, + hm < 0, hm hn > 0,
(2b)
m2
(2c)
(2d)
2/ E (0, 1}.
(2c)
where the logical constraints in Equation (2b) and Equation (2c) are translated into big-M constraints
by MIP solvers. To verify the conrectness of this formulation, observe that constraints (2b) and (2c)
in conjunction with the fact the binary 25th ensures that at most one of hy and hy non-zero.
3

---

Furthermore, since both hn and hif are non-negative, if >m w/j 1ii
w//-1 + +b > 0, then it
follows that hm > 0 and h = O. If negative, then h7 = 0 and hy > 0. Thus, we have that if the left-hand side of (2a) is positive, hm will be positive; if it negative, then hy = O; this is an exact representation of the ReLU function.
3 Related Work
3.1 Machine Learning for Nested Optimization
Machine learning has recently been employed solve nested optimization problems; by "nested", we mean optimization problems whose objective or constraints involve another optimization. For example, Nair et al. [2018], Shen et al. [2021], Jiang et al. [2021], Xiong and Hsieh [2020], Shao et al. [2022] directly predict binary or continuous solution vector. The major limitation with predicting solutions directly the inability to handle variable integrality and hard constraints. In addition, only Nair et al. [2018] consider 2SP, whereas the others focus on bi-level problems with a single inner optimization, rather than the expectation as in stochastic programming. For stochastic programming, there has been significant interest in the integration of learning to enhance prevalent solution techniques. We specifically discuss three areas of related work: learning-ena enabled optimization, learning- -aasdd algorithms for stochastic programming, and scenario reduction for stochastic programming.
The line of work on learning-enabled enabled optimization [Deng and Sen, 2022, Liu et al., 2022, Diao and Sen, 2020] introduced "predictive stochastic programming" to leverage contextual information when formulating SP models. This is in contrast to our approach, which leverages predictions reduce computing times non-contextual 2SP setting. That being said, Neur admits extensions to the contextual setting by including the context information during training.
In recent years, several studies have explored the use of integrating predictions within stochastic programming algorithms for computational improvements. Donti et al. [2017] proposed an end-to- end approach directly optimize task-loss for contextual stochastic programming problems by differentiating through the argmin operator, specifically for strongly convex problems. Dai et al. [2022] developed a model solve multi-stage linear optimization problems by learning the piece- wise value function of the nested problems. Larsen et al. [2022] leveraged predictions to improve an exact decomposition based algorithm for 2SP. Neur differs from these approaches as it can be applied to problems with both hard constraints and integer/non-linear second-stage problems.
Lastly, another related research direction for learning-based stochastic programming is scenario reduction, which reduces the complexity of the stochastic programming problem by finding smaller set of "representative scenarios". Many of these approaches [Dupačová et al., 2003, Römisch, 2009, Beraldi and Bruni, 2014, Prochazka and Wallace, 2020, Keutchayan et al., 2021] perform some form of clustering to reduce the number of scenarios and then solve a smaller surrogate problem with these scenarios. Recently, Wu et al. [2022] used conditional variational autoencoder to learn scenario embeddings and perform clustering on them for scenario reduction. To find representative scenarios, they use semi semi-supervised learning with respect to the second-stage cost. However, these predictions are not leveraged explicitly the optimization as is done with Neur Bengio al. [2020) predicts representative scenario for an input scenario set and use it to form a smaller surrogate problem. They show that using the predicted representative scenario, a near-optimal first-stage decision can be obtained by solving the surrogate. However, their method requires some domain expertise as it relies on the problem structure to build the representative scenario for training.
3.2 Neural Network Embeddings
Neur can be broadly classified as both a learning- based scenario reduction approach and learning- accelerated heuristic for stochastic programming. The reason for this is that Neur reduces the computational complexity introduced by the scenarios by computing compact representation that is then leveraged to formulate an approximation to the EF. We specifically leverage the recent line of work by Cheng et al. [2017], Tjeng et al. [2017], Fischetti and Jo [2018], Serra et al. [2018) 18, which studies the problem of embedding trained neural network with ReL.U activation into a MIP. The works of Anderson et al. [2020] and Grimstad and Andersson [2019] present MIP encoding

---

Input
Networkk
decison
Intermediste
"aUU Network used MIP-NN
X
Meen aggregation
( 1=1
ANLL Network
2 px Ex)
Ex
T E
Sonmario Embedii me Netwont
Aggiegation Netwont
T
V
Scenarios
Intermeciate ane uner ambeddingg
Aggregeted Serean
Final scenaric #mbestting
Figure NN-E architecture diagram.
formulations with tighter LP relaxations by appropriately setting the big-M constraints, leading to reduced solving time. The growing interest in embedding predictive models in MIPs has led to the development of libraries such as JANOS [Bergman et al., 2022] and OMLT [Ceccon et al., 2022]. Say et al. [2017], Grimstad and Andersson [2019], Murzakhanov et al. [2020]. Katz et al. [2020]. Kody al. [2022] propose the use of embedded neural networks to formulate surrogate MIPs intractable and non-linear constraints in optimization problems. To the best of our knowledge, Neur2SP is the first approach that employs this technique in stochastic programming or more generally for the simplification of nested optimization problems.
4 The Neur2SP Framework
In this section, we present two neural architectures, corresponding surrogate problems that ap- proximate given 2SP, and a data collection strategy. Figure summarizes the Neur framework.
4.1 Neural Network Architectures
We propose two distinct neural architectures for predicting the second-stage costs: NN-E approximates the expected value of the second-stage cost of a set of scenarios, whereas NN-P approximates the per-scenario value of the second-stage cost for single scenario.
NN-E (Figure 2) learns a mapping from (x, (E, EK_ PxQ(x, Ex). In words, the model takes in first-stage solution x and any finite set of scenarios sampled from E, and outputs prediction of the expected second-stage objective value. We embed the scenario set { into a latent space by passing each scenario, independently, through the same neural network 1 then performing mean- aggregation over the resulting K embeddings. The aggregated embedding is passed through another network, 22² obtain the final embedding of the scenario set, εx. This embedding, representing the scenario set A-la-DeepSett [Zaheer et al., 2017], is appended to the input first-stage decision and passed through ReLU ferwar network a to predict the expected second -tage value. Hence, the final output such that "x (² y (ps, Ex))) R ΣX= P&Q(x, &.). Note that the embedding networks, 1 and 2 can be arbitrarily complex as only the latent representation embedded into the approximate MIP. Also, although / is trained using K scenarios, once the networks are trained, they can be used with any (potentially much larger) finite number of scenarios.
NN-P learns mapping &. from (x, 6 P is learned, we can approximate the expected second-stage objective value for any finite set of scenarios as Ek= Qxx Ex) RJ Ek P (x,""((x, Ex). 4 is a feed-forward neural network with input given by the concatenation and E.
Q(x E) for & sampled from E. Once the mapping
4.2 Neural Network Embedding for 2SP
We now describe the surrogate MIP for both the NN-E and NN-P learning models from the preceding section. Let A represent the number of predictions made the neural network. For the NN-E case,
5

---

A = as we only predict the expected second-stage value for a set of scenarios. In the NN-P case,
A K as we predict the second-stage value for each scenario. In this section, we use [M] to denote (1...., M) for M E Z4..
Let h represent the ReLU output for the j-th hidden unit in the m-th hidden layer for output X, for all m E [e-11 [1-1], / E [dm], and À E [A]. Suppose Ai is a slack variable used to model the LCLU output for the j-th hidden unit in the m-th hidden layer for scenario k; for all m E [e [e- 11. E [dm] and X E [A]. Let 23 =a be a binary variable used to ensure that at most one of h and hit are non-zero. This variable is defined for all m [e- 11. j E [dm], and À [A]. Suppose Bx is the X-th prediction by the neural network, for all X E [A].
With the above variables we can define an approximation to EF as given in Equation (3). The objective function (3a) minimizes the sum of the cost of the first-stage decisions and the approximate cost of the second-stage value. Constraints (3b)-(3d) propagate first-stage solution x to the output of the neural network for each scenario. Constraints (3e)-(3h) ensure the prediction of the neural network is respected. Constraint (3i) ensures the feasibility of the first-stage solution.
In this approximation, we introduce a number of additional variables and big-M constraints. Specif- ically, for a neural network with H hidden units, we introduce A - HH additional binary variables for 2j m... In addition, we introduce 2 A H continuous variables for i and h. Lastly, we require an additional A variables for the output of the network. Although the number of variables we introduce in this approximation is quite large, we hypothesize that the resulting MIP will be easier to solve than the extensive form, in particular, when the second-stage problem is nonlinear. In the remainder of the paper, we refer to the surrogate MIP given in (3) as MIP-NN.
A min cxx + Σ PASA
(3a)
s.t.
0 [x, Exli + = n1. - ng4
+
A EjE [A], (3b)
w/y 1- 'h. 1,1 + +b7 h..... hmg
1
Am E 31 11,5 E [dm)] A E [A], (3c)
de
Wi 1/ + +6 S 3x
(3d)
A
1 hm
A m E [e 11,j E [dmm], A E [A],
(3e)
3)
3 m, 0 = h3 im.. 0
Vm e [L - 11,1j E [dm.]. X E [A],
(3f)
3j mnd E t0, 1}
V m E [[_1],, E [dm]] X E [A],
(3g)
R.m.A, 11. J.m.A 20 0
A m E [e 11,5 E [d X E [A], (3h)
x E X
(3i)
4.3 Data Generation
A diverse dataset of input-output pairs is needed to train Neur2SP's supervised second-stage value approximation. To generate such a dataset for given 2SP problem, we adopt an iterative procedure. We begin by generating a random feasible first-stage decision. For the NN-E case, we sample a set of scenarios with random cardinality K' from the uncertainty distribution. Here, K' should be chosen to balance the trade-off between the time spent to generate sample of second-stage values for a given first-stage solution and the time to estimate the expected second-stage value for a set of first-stage decisions in given time budget. Specifically, if K" is large, then on average more time will be spent in determining the expected value using a large number of scenarios, while for a small K', the first-stage decision space will be explored more since expected value estimates would be

---

Problem
First stage
Second Stage
Objective
Constraints
Objective Sense
CFLP
Binary
Binary
Linear
Linear
Minimization
INVP
Continuous
Binary
Linear
Linear
Minimization
SSLP
Binary
Binary
Lineur
Linear
Minimization
PP
Binary
Continuous
Bilinear
Bilinear
Maximization
Table I: Problem class characteristics.
obtained faster. For given input, i.e., first-stage decision and set of scenarios, we then compute label by calculating the expected second-stage value = Pk Qx.
For the NN-P casc, at each iteration of the data generation procedure, we sample single scenario from the uncertainty distribution. For given input of first-stage decision and scenario we generate label by calculating its second-stage value Q) Last, the input-output pair is added to the dataset.
This data generation procedure is fully parallelizable over the second-stage problems to be solved.
4.4 NN-E vs. NN-P Trade-offs
The NN-E and NN-P architectures exhibit trade-offs in terms of the learning task and the resulting surrogate optimization problem.
Training. In data collection, both models require solving second-stage problems with fixed first- stage solution to obtain the label. A sample in for NN-P requires solving only a single optimization problem, whereas sample for NN-E requires solving most K' second-stage problems. As this process is offline and highly parallelizable, this trade-off is easy to mitigate. As for training, NN-E operates on a subset of scenarios which makes for an exponentially larger input space. Despite the large input space, our experiments show that the NN-E model in the training converges quite well and in many cases the embedded model outperforms the NN-P model.
Surrogate Optimization Problem. As the ultimate goal is embedding the trained model into MIP, the trade-off in this regard becomes quite important. Specifically, for K scenarios, the NN-P model will have K times more binary and continuous variables than the NN-E model. For problems with a large number of scenarios, this makes the NN-E model much more appealing, smaller and likely faster to solve. Furthermore, it allows for much larger networks given that only single copy of the network is embedded.
5 Experimental Setup
All experiments were run on computing cluster with an Intel Xcon CPU E5-2683 and Nvidia Tesla P100 GPU with 64GB of RAM (for training). Gurobi 9.1.2 [Gurobi Optimization, LLC, 2021] was used as the MIP solver. Scikit-learn 1.0.1 [Pedregosa et al., 2011 1] and Pytorch 1.10.0 [Paszke et al., 2019] were used for supervised learning. The code to reproduce all of the experiments is available at https://gtt thub. com/khalin wwthhalll-esserrrleeeee
2SP Problems: We evaluate our approach on four 2SP problems that are commonly considered in the literature: a two-stage stochastic variant of the Capacitated Facility Location Problem (CFLP) [Cor- nuéjols et al., 1991] J. an Investment Problem (INVP) [Schultz et al., 1998], the Stochastic Server Location Problem (SSLP) [Ntaimo and Sen, 2005], and the Pooling Problem (PP) [Audet et al., 2004, Gupte al., 2017, Gounaris et al., 2009, Haverly, 1978]. Table I summarizes the types of first and second-stage variables for these problems and Appendix B includes their detailed descriptions.
We consider two baselines. The first is EF, which is perhaps the only generic approach that can be applied for both integer and nonlinear second-stage problems. We limit the solving time of EF to hours. Additionally, we compare against embedded trained linear regressor rather than a neural network, but defer these results to Appendix as the solution quality is quite poor in comparison the neural network models.
Baselines:
Model Dataset Selection: As is common in supervised learning, model selection and the size of the training set can have significant impact model performance. We present detailed experiments
7

---

Problem
Data Generation Time
Training Time
Total Time
NN-E
NN-P
NN-E
NN-P
NN-B
NN-P
CFLP 10,
1,823.07
13.59
667.28
127.12
2,490.35
140.71
CALP 25 25
4.148.83
112.83
2,205.23
840.07
6,354.06
952.90
CTLP_50_550
7,697.91
135.57
463.71
128.11
8,161.62
263.68
SSLP 10_50
942.10
22.95
708.86
116.17
1,650.96
139.13
SSLP 15 45
929.27
16.35
1,377.21
229.42
2,306.45
245.77
SSLP_5 ___2
860.74
13.18
734.02
1,594.75
160.62
INVP B
8,951.27
4.17
344.87
1,000.14
9,296.13
1,004.3
INVP_B ___
9.207.90
4.22
1.214.54
607.49
10,422.43
611.71
INVP LE
8,759.83
4.34
2,115.25
680.93
10,875.08
685.27
INP_LL
8,944.65
3.32
393.82
174.26
9,338.47
177.58
1,202.11
14.86
576.08
367.25
1,778.19
382.11
Table 2: Computing times (in seconds) for data generation and training. Data was generated in parallel with 43 processes.
for model selection and dataset sizing in Appendix F. As a brief summary, we use random search over 100 hyperparameter
for model selection, and observe that accuracy on a validation set rather insensitive to hyperparameter choices. For the size of the dataset, we observe diminishing returns when increasing the size beyond 5000 samples.
Data Generation & Supervised training times: : As the data generation and training can be done offline and are both parallelizable, we report the total times in Table 2 and defer more specific timing details to Appendix C. We note that for data generation, single sample can be obtained in less than two seconds for all instances, and in many cases much faster. The training times are within the range of 120 to 2100 seconds. For the NN-E data generation, we choose K' 100, a number of scenarios which was quick to label while exposing the model to reasonably large number of scenarios in some cases. The combined time for data generation and model training typically less than hours (i.e., the time given to EF) and depending on the problem, may be much less.
6 Results & Discussion
In this section, we report the results of Neur2SP across the four problem settings. As is standard in 2SP, we evaluate single "base" instance across varying scenario sets and sizes. For example, in CFLP, and for a "base" instance with 10 facilities and 10 customers, one can generate an instance by sampling any number of scenarios. An important advantage of our approach that we can apply single trained model to an instance with an arbitrary number of scenarios. For example, the same trained model is used for CFLP 10_101011__00 _0_ 100,,00,000000000 1000)
Tables 3 through 6 report the gaps between approaches, solving times, and the time which EF takes to achieve the same solution quality as NN-E and NN-P. In addition, include supplementary results with the objective values in Appendix D and non-aggregated results for the SSLP SIPL.ih jib instances in Appendix E. For SSL.P and CFLP, each row represents mean statisties across 11 and 10 instances generated by sampling different scenario sets of a given size, respectively. However, for INVP and PP, each row represents the statistics across instance. Originally, both these problems have infinite support as the uncertainty distributions are assumed to be continuous. To manage the complexity, these distributions are typically transformed to have finite support by uniformly sampling equidistant points over the continuous domain. We adopt this same procedure from the literature, leading to static set of scenarios for a given scenario set size.
6.1 Discussion
Tables 3-6 show that NN-E is significantly faster than other approaches, with a minimum and maximum solving time of 0. and 1.66s respectively, across all problems. This highlights the scalability of the NN-E in terms of problem size and type, which is expected as the size of the resulting MIP is independent of the number of scenarios. Also, the objective difference is less than 5% in most cases, with a minimum of -102% and a maximum of 13. 13.78% These differences are inversely proportional to the scenario set size, which indicates that the NN-E is able to generalize on larger scenario sets, even though it was trained with maximum of 100 scenarios per data point. EF
8

---

Problem
Obj. Difference (S)
Solving
time
EP-NN-B
EF-NN-P
NN-E
NN-P
EF
NN-E
NN-P
CRLP 10 10_ 100
2.58
1.65
0.38
8.28
4,410,60
8,87
(0) 12.69
(0)
CFI.P 10 10 500
2.41
0.94
0.60
206,30
10.800.17
415.89
(0)
2,034,73
(0)
CFLP_10_100 10_0000000000000
0.94
856.77
10,800.87
580.50
(0)
7,551.00
(8)
CFLP_25 25 100
-0.75
-0.75
0.44
4.86
10,800.06
(10)
(10)
CFLP
-3.62
-3.62
26.41
10,800.14
(10)
CFLP_25 25_ 1000
-1.52
-1.32
0.58
54.45
10,800.36
(10)
(10)
CFLP_50 SELP_550_50_1111
-0.43
-1.29
1.66
21,10
10,800.05
5,637.99 .99
(6)
2,334.04
(9)
CFLP_ 50 50 500
-9.58
-10.71
1.25
173.63
10,806.15
(10)
(10)
CFLP_50 50_5000000000 1000
-16.62
-17.50
1.44
572.12
10,805.82
(10)
(10)
Table 3: CFLP results:
each row represents an average over ten 2SP instances with varying scenario sets. "Obj. Difference" for method (NN-NN-E, NN-P) is the percent relative objective value of (NN-E, NN-P) to EF; a negative (positive) value of -g% (g%) indicates that (NN-E, NN-P) finds a solution that is 9% better (worse) than EF's for the minimization problem. "Solving Time" is the time in which (NN-E, NN-P, EF} are solved to optimality. A time of ~ 10,800 implies that the solving limit was reached. "EF time to" is the time which EF achieves a solution of the same quality as (NN-E, NN-P). To the right in parentheses is the number of instances for which EF failed to find a solution that is as good as (NN-E, NN-P). EF did not find any feasible solution, then the entry is left as "-", All times are in seconds.
Problem
Obj, Difference (%)
Solving Time
EF time to
EF-NN-E
ER-N-P
NN-E
NN-P
EF
NN-E
NN-P
SSLP 10_50_50
0.00
0.00
0.11
5.83
10,800.48
228. 06
(0)
228.06
(0)
SSLP 10_50_100
-0.00
-0.00
0.11
13.09
10,800.21
145.35
(0)
145,35
(0)
SSLP 10_50_
-0.00
-0.00
0.14
129.44
10,802.82
7,359.85
(4)
7,359.85
(4)
SSLP_10_50 10.50_1100 1000
-55.21
-55.21
0.13
466.38
10,800.47
(11)
(11)
SSLP 10__00000000000
-102.69
-102.69
0.14
2,182.31
10,800.17
(11)
SSI P 15 45_5
3.10
18:71
0.32
0.34
2.54
0.75
(0)
0.12
(0)
SSLP 15__5_10
2.98
18.47
0.31
0.58
1.976.62
2.72
(0)
0.20
(0)
SSL 44__5
2.53
18.90
0.86
2,052,76
(0)
0.34
(0)
SSLP S 25 50
0.12
1.78
0.20
1.14
2.24
1.94
(0)
1.97
(0)
SSLP 5 5_25_100
0.02
0.18
1.83
8.43
7.75
(1)
Table 4: SSLP results: each row represents average over eleven 2SP instances with varying
scenario sets, one of which being the instance from Ahmed et al. [2015]. Columns are as in Table 3.
takes significantly longer to reach solution quality similar to NN-E, often on the order of minutes to 3 hours. For many larger CFLP and SSLP instances, EF finds worse solutions than NN-E even after hours. Not only is NN-E as good or better in solution quality, but also orders of magnitude faster.
For the NN-P, we can observe that the solving time is directly proportional to the size of the problem. However, for the largest INVP instances, it times out without even generating a feasible solution (Table 5). This is expected as we need to embed the trained neural network once per scenario, limiting scalability. In terms of objective differences, we can observe that the difference improves with the increase in instance size for CFLP and SSLP, whereas no clear trend is visible for For INVP. However, the objective differences do not exceed 5% in most cases. For PP, the objective difference is around 40%, indicating that the NN-P is not able to generalize, whereas NN-E performs very well. One important advantage for NN-P over NN-E is the fact that the time required for data generation and training is notably less. In settings with limited parallel computing resources or time NN-P may be a more appropriate choice.
7 Conclusion
Two-stage stochastic programming is a powerful modeling framework for decision-making under uncertainty. These problems are hard to solve in practice, especially when the second-stage problem is a MIP or NLP. Finding good feasible solutions quickly thus becomes extremely important.
To that end, we proposed Neur2SP, a learning- general, and structure- -agnosicc approach which approximates the second-stage value function to form an easy-to-solve surrogate problem. The four problem classes we have tackled are (1) widely used in the literature, (2) vary in the types of first and second-stage problems, and (3) span wide range in terms of number of variables, constraints, and scenarios. Through our experiments, we show that Neur2SP achieves high-quality solutions quickly, especially for larger instances. In 1-2 seconds, model trained in the Neur2SP framework can find

---

Problem
Obj. Difference (%)
Solving Time
time to
EF-NN-E
EF-NN-P
NN-E
NN-P
EF
NN-E
NN-P
INVP B_E
9.54
3.01
0.36
0.34
0.02
0.02
0.02
INVP E
7.54
2.00
0.31
0.53
0.04
0.03
0.03
INVP F.3
2.72
4.96
0.30
9.53
0.08
0.02
0.02
INVP B E_
1.37
2.42
0.33
86.42
1.69
0.06
0.02
INVP 441
2.80
2.43
0.37
4,742.19
117.59
0.78
1.15
INVP B. E 1681
1.36
0.34
10,800.00
17.41
0.00
INVP 10000
0.36
10,803,98
INVE B. H
8.81
9.50
0.46
0,25
0.01
0.01
0.01
INVP 9
5.04
5.04
0.30
0.57
0.03
0.02
INVP 36
1.61
1.61
0.26
6.79
1.29
0.01
0.01
INVP H. 121
1.77
1.77
0.33
45.89
34.69
0.01
0.01
INVP HL441
2.13
5.50
0.28
1,870.42
217.46
2.21
0.21
INVP B. 1681
-0.71
0.36
10,800.01
0.00
INVP 1000
-2.72
0.36
10,800.05
INVP E
12.83
0X00
0.38
0.23
0.01
0.01
0.01
7.40
INVP L 36
5.48
5.17
0.27
1,39
0.04
0.01
0.01
INVP LE 121
5.30
4,49
0.29
49,51
1.65
0.02
INVP LE 441
3,00
0.68
0.26
2,049,93
46.92
0.08
0.10
INVP E 1681
1.31
3.08
0.26
10,834.53
10,800.00
0.41
0.41
INVP_ 10000
-1.35
0,30
10,800,10
0.00
INVP I 4
13.78
12.16
0.35
0.21
0.02
0.01
0.01
INVP L
9.12
0.37
0,31
INVP L 36
4.97
3.44
0,36
1.99
1.27
0.03
0.03
INVP LH 121
4.01
4.99
0.32
23.10
7.43
0.07
0.07
INVP L 441
3.15
3.15
0.32
1,231,48
10,800.00
0.33
0.33
INVP 1.._H_IIG 1681
-0.34
0.11
0.33
10,816.89
10,800.02
252.70
IVV___H. 10000
-1.60
0.38
10,802.10
0.00
Table 5: INVP results: each row represents a single instances. Columns are as in Table 3.
Problem
Obj. Difference (%)
Solving Time
EF time to
EF-NN-E
EE-NN-P
NN-E
NN-P
EF
NN-E
NN-P
PP 125
3.25
36.64
1.51
144.08
10,800.00
10,717.05 7.05
2.48
216
9.06
254.94
364.90
59.79
PP_343
0.67
40.85
1.46
570.64
10,800.00
1,450.54
9.12
PP PP_512
8.69
39.77
1.60
1,200.37
10,800.01
167.77
13.80
PP_729
1.38
37.98
1.62
3,440.19
10,800.01
5,867.67
36.34
PP 1000
5.92
10,853.59
10,800.00
1,596.22
210.48
Table 6: PP results: each row represents a single instances. Columns are as Table
solutions of the same or better quality than the most generic method in the literature, EF, with the latter taking minutes to hours.
In terms of future work, this methodology can extended in many directions. Further innovations in the NN-E model architecture may improve already positive results. Another direction is the extension of the general idea of embedding trained models into other complex optimization problems, such bilevel optimization multi-stage stochastic programming.
Another direction for future work is more comprehensive comparison Neur2SP with algorithms that are specialized to a given problem class. However, we note that on SSLP instances, the computing times progressive hedging IRockafellar and Wets, 1991], widely used heuristic for 2SP, on the order of hours ['Torres al., 2022]. These experiments not directly comparable they were run on different hardware. However, this would not meaningfully impact the several order of magnitude reduction in solving time achieved by our approach.
Lastly, in this work, we propose NN-E and NN-P, however, a natural middle ground between these models is a clustering approach which embeds trained model for subset of scenarios, rather than single or the entire scenario set evaluation time.
Ackmowledgments: Bodur would like to acknowledge support from an NSERC Discovery Grant. Dumouchelle, Patel, and Khalil acknowledge support from the Scale Al Research Chair Program and an NSERC Discovery Grant.
10

---

References
Mattco Fischetti and Jason Jo. Deep neural networks and mixed integer linear optimization. Con- straints, 23(3):296-300 2018.
Vinod Nair, Dj Dvijotham, lain Dunning, and Oriol Vinyals. Learning fast optimizers for contextual stochastic integer programs. In UAI, pages 591-600, 2018.
Jiayi Shen, Xiaohan Chen, Howard Heaton, Tianlong Chen, Jialin Liu, Wotao Yin, and Zhangyang Wang. Learning a minimax optimizer: pilot study. In International Conference on Learning Representations, 2021. URL https: https://opennteeeeeee /ttp:///wepe/eeee/e/eeeeee net/ formmf/dddddddddDil666
Haoming Jiang, Zhehui Chen, Yuyang Shi, Bo Dai, and Tuo Zhao. Learning defend by learning attack. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Staristics, volume 130 of Proceedings of Machine Learning Research, pages 577-585. PMLR, 13-15 Apr 2021. URL https: http::/:///cocednnggs. mlr.. press/v130/ jta//jianggg ang21a. html.
Yuanhao Xiong and Cho-Jui Hsieh. Improved adversarial training via learned optimizer. In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm, editors, Computer Vision ECCV 2020, pages 85-100, Cham, 2020. Springer International Publishing.
Zhihui Shao. Jianyi Yang, Cong Shen, and Shaolei Ren. Learning for robust combinatorial opti- mization: Algorithm and upplication. In JEEE INFOCOM 2022 IEEE Conference on Computer Communications, pages 930-939, 2022. doi: 10.1 1011099IFO00044480000200..7777
Yunxiao Deng and Suvrajeet Sen. Predictive stochastic programming. Computational Management Science, 19(1):65-999 98, 2022.
Junyi Liu, Guangyu Li, and Suvrajeet Sen. Coupled learning enabled stochastic programming with endogenous uncertainty. Mathematics of Operations Research, 47(2)11611-1705, 2022.
Shuotao Diao and Suvrajeet Sen. Distribution-free algorithms for learning enabled optimization with non-parametric estimation. Management Science, 66(3); 1025-104,, 2020.
Priya Donti, Brandon Amos, and J Zico Kolter. Task-based end-to-end model learning in stochastic optimization. Advances in Neural Information Processing Systems, 30, 2017.
Hanjun Dai, Yuan Xue, Zia Syed, Dale Schuurmans, and Bo Dai. Neural stochastic dual dynamic programming. International Conference on Learning Representations, 2022. URL. https: ///pe//reviw..nee///eeee htt.:/eeeoooomddddiii/eeeeeeeeee id=aiskP
Eric Larsen, Emma Frejinger, Bernard Gendron, and Andrea Lodi. Fast continuous and integer L-shaped heuristics through supervised learning. arXiv preprint arXiv:2205.0089) 2022.
Jitka Dupačová, Nicole Gröwe-Kuske and Werner Römisch. Scenario reduction in stochastic
programming. Mathematical Programming, 95(3):493-51) 2003.
Werner Römisch. Scenario reduction techniques in stochastic programming. International Symposium Stochastic Algorithms, pages 1-14. Springer, 2009.
Patrizia Beraldi and Maria Elena Bruni. A clustering approach for scenario tree reduction: an application to stochastic programming portfolio optimization problem. Top, 22(3):934-949, 2014.
Vit Prochazka and Stein W Wallace. Scenario tree construction driven by heuristic solutions of the optimization problem. Computational Management Science, 17(2):7773077, 2020.
Julien Keutchayan, Janosch Ortmann, and Walter Rei. Problem-driven scenario clustering in stochastic optimization. arXiv preprint arXiv:2106.11711 2021.
Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Learning scenario representation for solving
two-stage stochastic integer programs. International Conference on Learning Representations, 2022. URL https: / http///wppeeeeeeee//e/e/ee http:///eeeooorrr/o//lo/la.aa...

---

Yoshua Bengio, Emma Frejinger, Andrea Lodi, Rahul Patel, and Sriram Sankaranarayanan, A learning-bat baased algorithm to quickly compute good primal solutions for stochastic integer programs. In International Conference Inlegration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 99-111. Springer, 2020.
Chih- Hoog Cheng, Georg Nührenberg, and Harald Ruess. Maximum resilience of artificial neural networks. In International Symposium on Automated Technology for Verification and Analysis, pages 251-268. Springer, 2017.
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. arXiv preprint arXiv:1711.07356 2017.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In International Conference on Machine Learning, pages 4558-4566. PMLR, 2018.
Ross Anderson, Joey Huchette, Will Ma, Christian Tjandraatmadja, and Juan Pablo Vielma. Strong mixed-integer programming formulations for trained neural networks. Mathematical Programming, pages 1-37, 2020.
Bjarne Grimstad and Henrik Andersson, ReLU networks as surrogate models in -ixed-integer linear programs. Computers & Chemical Engineering, 131: 2019.
David Bergman, Teng Huang, Philip Brooks, Andrea Lodi, and Arvind U Raghunathan. JANOS: an integrated predictive and prescriptive modeling framework. INFORMS Journal on Computing, 34 (2):807-816 2022.
Francesco Ceccon, Jordan Jalving, Joshua Haddad, Alexander Thebelt, Calvin Tsay, Carl D Laird, and Ruth Misener. OMLT: Optimization machine learning toolkit. arXiv preprint arXiv:2202.02414, 2022.
Buser Say, Ga Wu, Yu Qing Zhou, and Scott Sanner. Nonlinear hybrid planning with deep net learned transition models and mixed-integer linear programming. In IJCAI, pages 750-756, 2017.
Ilgiz Murzakhanov, Andreas Venzke, George Misyris, and Spyros Chatzivasilciadis. Neu- ral networks for encoding dynamic security-constrained optimal power flow. arXiv preprint arXiv:2003.07939 2020.
Justin Katz, losif Pappas, Styliani Avraamidou, and Efstratios N. Pistikopoulos. The integration of explicit MPC and ReLU based neural networks. IFACC-PapersOOnLinee URL https:// 21 IFAC World
2020. ISSN 2405-8963. doi: cttp://cccccc//tccccaaaa//////s. www www.seeieeediret.cco www/ Congress.
Alyssa Kody, Samuel Chevalier, Spyros Chatzivasileiadis, and Daniel Molzahn. Modeling the AC power flow equations with optimally compact neural networks: Application to unit commitment. Electric Power Systems Research, 103:10 2022. ISSN 0378-7796. doi: https://doi.rg/// 10. 10166f.cpst.2022.10222 URL ot $0378879622200477..
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander J. Smola. Deep sets. In Isabelle Guyon, Ulrike von Luxburg, Samy Ben- gio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, edi- tors, Advances in Neural Information Processing Systems 30: Annual Conference Neu- ral Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 3391-3401, 2017. URL https://proceedingg wwwpeeddiinnn.uuuiiss.eeee httpsscccpppppp//ee// 222247447aaaa22778888888001800.2 hat.aaad000004422f--brbeetetttt Abstract html.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2021. https:/www..urrbb.ccmm
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning Python. Journal of Machine Learning Research,
12:2825-28345 2011.
12

---

Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. 7achary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, nigh-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019. http://papes..neuiiscccpppppppp www.riis.ccppppe//000 wwpptooc--n-iiperraaae hugd--prforrann--de--leeenngg -iinrggiibbrardd...
Gérard Cornuéjols, Ranjani Sridharan, and Jean-Michel Thizy. A comparison of heuristics and relaxations for the capacitated plant location problem. European Journal of Operational Research, 50(3):280-297 1991.
Rüdiger Schultz, Leen Stougie, and Maarten H Van Der Vlerk. Solving stochastic programs with integer recourse by enumeration: framework using Gröbner basis. Mathematical Programming. 83(1))229-252, 1998.
Lewis Ntaimo and Suvrajeet Sen. The million-variable "march" for stochastic combinatorial opti- mization. Journal of Global Optimization, 32(3):385 -0000 2005.
Charles Audet, Jack Brimberg, Pierre Hansen, Sébastien Le Digabel, and Nenad Mladenović. Pooling problem: Alternate formulations and solution methods. Management Science, 50(6):761-776 2004.
Akshay Gupte, Shabbir Ahmed, Santanu S Dey, and Myun Scok Cheon. Relaxations and discretiza- tions for the pooling problem. Journal of Global Optimization, 67(3):631-669, 2017.
Chrysanthos E Gounaris, Ruth Misener, and Christodoulos A Floudas. Computational comparison of piecewise-linear relaxations for pooling problems. 48(12):5742-5577 2009.
Co A Haverly. Studies of the behavior of recursion for the pooling problem. Acm sigmap bulletin, 195):19-28, 1978.
Shabbir Ahmed, R Garcia, N Kong, Ntaimo, G Parija, F Qiu, and S Sen. SIPLIB: A stochastic inte- ger programming test problem library. https://www..3 isye gatech. "ataa"samedd/////a ssahee/sspppi// 2015.
R Tyrrell Rockafellar and Roger J-B Wets. Scenarios and policy aggregation in optimization under uncertainty. Mathematics of operations research, 16(1):119-147, 1991.
Juan Torres, Can Li, Robert M Apap, and Ignacio Grossmann. review on the performance of linear and mixed integer two-stage stochastic programming software. Algorithms, 15(4):103, 2022.
Niels van der Laan and Ward Romeijnders. A loose Benders decomposition algorithm for approxi- mating two-stage mixed-integer recourse models. Mathematical Programming. 190(1):61-7944 2021.
Xiang Li, Emre Armagan, Asgeir Tomasgard, and Paul I Barton. Stochastic pooling problem for natural gas production network design and operation under uncertainty. AIChE Journal, 57(8): 2120-2135, 2011.
13

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A] You strongly encouraged to include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license the code and datasets? [No] The code and the data proprietary.
Did you include the license the code and datasets? [N/A]
Please do not modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (cither in the supplemental material or as URL)? [Yes] All code to reproduce the experiments is available https: ///nonyooomus....// www.:eouu.........oom.mm 4open. science/// 437E.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] The both training and evaluation are done over varying configurations and realizations of randomness.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] These are detailed in Section 5 and the Appendix.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] All software used in the development has been cited
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "rYtXjbEct_", "reviewer": "Reviewer_fXmS", "summary": "The paper introduces a heuristic method for two-stage stochastic optimization problems that approximates the value function of the second stage with a neural network. Notably, the problem may be mixed-integer, possibly nonlinear, in the second stage, which can make the problem particularly challenging. The value function for a problem is learned in advance by sampling scenarios and training a neural network, which is embedded into the first-stage problem as a MIP. Computational results on a variety of stochastic optimization instances show positive results compared to the extensive form of the problem.", "questions": "No questions or suggestions besides the above. A minor detail is that Equation (3) should be in section 4.2.", "limitations": "The paper should be more explicit regarding data generation and training time as discussed above, but there are no limitations on societal impact that need to be addressed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper provides an effective heuristic to solve two-stage stochastic optimization problems, which has several important applications in Operations Research. An appealing property of this method is its generality, as it can be applied without any modifications even when the second stage is mixed-integer or nonlinear, which often makes the problem more challenging. The computational experiments are reasonably extensive and positive: the method can produce better results than the extensive form for certain large-scale instances, particularly when the number of scenarios is large, and sometimes even when taking into account data generation and training time sequentially. There are also instances where the method does not perform as well when taking training time into account (INVP), which is useful to have in the paper. The paper is overall well-written and clear. \n\nMy concerns with the paper are the following:\n\n1. The text is not very explicit when taking into account the data generation and training time, often implicitly treating as if they were not significant. Granted, they can be parallelized and the learned function can generalize to a larger number of scenarios, but that does not mean they can be dismissed, particularly because as is, this approximation is not intended to generalize to other instances. In particular, I do not believe it is fair to present the solution time in the abstract without proper contextualization (i.e. that this is without data generation and training time), and Section 6.1 should also be framed within this context. Ideally, I would prefer to see training and data generation times in the main text and I would encourage the authors to find space to fit them in, but I understand that this is difficult due to space issues. Another side effect of this is that, as is, at first glance the multicut approach does not seem very useful, but if you take into account data generation and training time it becomes more appealing particularly if one does not have access to broad parallelization capabilities, and perhaps this can be pointed out in Section 6.1.\n\n2. One limitation is that the paper does not compare with decomposition algorithms for two-stage stochastic optimization problems (e.g. Benders-based methods, progressive hedging). Decomposition methods tend to be substantially better than the extensive form in practice, and thus this paper does not answer the question of whether one should choose this approach over a decomposition method. It is also worth noting that this method is a heuristic and the extensive form is exact, which is not an ideal comparison (although I do appreciate the column \"EF time to\" in the tables). On the other hand, an argument is that the method presented in the paper is more general. In any case, although this is a limitation that should not be ignored, in my opinion this is outweighed by the rest of the paper.\n\nGiven that item 1 above is addressed, in my opinion this paper should be accepted. Not only this approach might be immediately applicable in practice for an important class of optimization problems (although not too clear due to the lack of comparison with decomposition methods), it can also be a useful stepping stone for further papers applying similar ideas. Therefore, I believe this paper can have a high impact in the field.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ps6pGcxv5hD", "reviewer": "Reviewer_9pYt", "summary": "This paper studies two-stage stochastic programs (2SPs). To address the computational complexity associated with the second-stage problem, the key idea is to use a neural network to approximate the second-stage value that facilitates the first-stage optimization. Both single-cut and multi-cut approximations are considered. Finally, Neur2SP is validated via experiments. ", "questions": "- The key idea of using a neural network to approximate the otherwise computationally-demanding second-stage problem has been well explored in a number of prior studies (not cited), so the novelty of this paper is rather limited. For example, the following papers use neural networks to approximate the solution of an inner maximization/minimization problem in worst-case robust optimization. While the specific contexts are a bit different from the one in this paper, the main technical novelty (i.e., using a neural network to speed up the inner optimization) in those papers still apply here.\n\n[1] Learning A Minimax Optimizer: A Pilot Study, ICLR'21.\n[2] Learning for Robust Combinatorial Optimization: Algorithm and Application, INFOCOM'22.\n[3] Learning to Defend by Learning to Attack, AISTATS'21.\n[4] Improved Adversarial Training via Learned Optimizer, ECCV'20.\n\n- The training distribution for the neural network to approximate the second-stage optimization is pre-generated/-determined, but it's entangled with the first-stage solution. As a result, the actual testing distribution (depending on the first-stage solution, which itself also depends on the second-stage approximation) can differ from the pre-generated distribution. This can raise convergence and/or out-of-distribution issues.\n\n- The single-cut vs. multi-cut tradeoff is only briefly touched without an in-depth analysis.\n\n- Secton 2.2 (Embedding Neural Networks into MIPs) is interesting, but this is taken directly from a prior study.", "limitations": "NA", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ The paper is fairly well written and easy to follow.\n+ 2SP potentially has practical applications.\n\nWeakness:\n- The key idea of using a neural network to approximate the otherwise computationally-demanding second-stage problem has been well explored in a number of prior studies (not cited), so the novelty of this paper is rather limited. For example, the following papers use neural networks to approximate the solution of an inner maximization/minimization problem in worst-case robust optimization. While the specific contexts are a bit different from the one in this paper, the main technical novelty (i.e., using a neural network to speed up the inner optimization) in those papers still apply here.\n\n[1] Learning A Minimax Optimizer: A Pilot Study, ICLR'21.\n[2] Learning for Robust Combinatorial Optimization: Algorithm and Application, INFOCOM'22.\n[3] Learning to Defend by Learning to Attack, AISTATS'21.\n[4] Improved Adversarial Training via Learned Optimizer, ECCV'20.\n\n- The training distribution for the neural network to approximate the second-stage optimization is pre-generated/-determined, but it's entangled with the first-stage solution. As a result, the actual testing distribution (depending on the first-stage solution, which itself also depends on the second-stage approximation) can differ from the pre-generated distribution. This can raise convergence and/or out-of-distribution issues.\n\n- The single-cut vs. multi-cut tradeoff is only briefly touched without an in-depth analysis.\n\n- Secton 2.2 (Embedding Neural Networks into MIPs) is interesting, but this is taken directly from a prior study.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "h-AwFrtU9s", "reviewer": "Reviewer_FXNT", "summary": "This paper presents an algorithm for producing feasible solutions for two-stage stochastic optimization problems. The main approach is to train a neural network to approximate the second-stage value function, and then embed this neural network into the first stage optimization problem. The authors present a deep learning architecture for learning the second-stage value function in both a \"single-cut\" and \"multi-cut\" setting, and discuss the data generation scheme for supervised learning. The computational section shows that the new \"single-cut\" method produces solutions that are typically roughly as good, and sometimes superior to, the \"extended formulation\", and arrives there in far less time (seconds vs. hours).\n\n", "questions": "* Have the authors considered how their method would generalize to problems with incomplete recourse? There is a glancing mention about artificially inducing relatively complete recourse in the appendix, but no other discussion. At the very least, please add a brief discussion about any assumptions on Y in the Preliminaries section, and a bit of discussion on the resulting limitations.\n* The \"Multi-cut\" subsection in 4.1 seems oddly abbreviated: is there nothing of interest to say about the architecture used? The equation block (3) also seems out of place.\n* How are valid(?) bounds computed for the input of the value function? This is a crucial ingredient necessary to determine the validity and computational performance of the end-to-end MIP formulation. In particular, my understanding from the paper is that the downstream MIP formulation only ever considers the latent space learned to represent the aggregated scenarios. How are bounds computed in this space?\n* I am curious if the authors have done any sensitivity analysis regarding the randomness inherent in the NN training procedure. More specificially, is there a wide variance in downstream performance for models trained with differing random seeds, for example? As intuitively it seems that the MIP optimizer will attempt to identify and take advantage of any artificial locally optimal \"artifact\" in the model, I am curious if randomness affects the presence or location of these artifacts, and if this ends up affecting the downstream performance. \n* In the computational section, can the authors provide more distributional information about the objective difference and solve time (and also, potentially, the number of \"time outs\")? I am especially curious about Table 5, and if the relatively poor performance of EF-MC w.r.t. objective difference can be attributed primarily to instances where it \"timed out\", or if the performance is just uniformly worse across the board.", "limitations": "The authors do not discuss the potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is clearly written, and presents an interesting and seemingly novel approach to a problem of great interest to the operations research community. The computational results suggest that the approach can offer a compelling tradeoff between solution quality and solve time.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bF9D59g7QKs", "reviewer": "Reviewer_D2XQ", "summary": "The authors propose a method for quickly obtaining high quality solutions to two stage stochastic programs (2sp) by training a neural network to estimate the second stage solution quality given the first stage solution, and then solving for the first stage solution by encoding the second stage estimator in the first stage MIP formulation, replacing the second stage value with it’s estimator. The authors evaluate on a variety of realistic 2sp instances with both linear and bilinear second stage problems demonstrating the flexibility of their approach to a variety of problems. Overall the authors demonstrate orders of magnitude of performance improvement over reasonable baselines that are equivalently general, making the class of 2sp problems much more accessible for realistic problems.", "questions": "Is it possible to compare against embedding other predictive models in the MIP formulation?\n\nAre there any settings in which the method didn't work, or instance in settings where the first or second stage is highly combinatorial?\n\nIs this approach applicable for bilevel optimization settings? What would be the potential pitfalls there?", "limitations": "The authors adequately addressed limitations and potential negative social impact", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The core strength of the paper is in its contribution to making a general class of 2sp problems computationally tractable in a sensible manner, combining the expressive power of neural networks with the computational power of MIP solvers to obtain high-quality solutions to 2sp problems quickly. The paper is very clear, original, and significant.\n\nAdditionally, the experiments and motivation are sound making this a great contribution to the literature of improving optimization performance with machine learning.\n\nI think the main area that could be improved is to investigate the sample efficiency of the approach and potential for other predictive models such as linear models or decision trees which could also be encoded as MIP. Otherwise, the approach seems to be sound and have great significance for the optimization community or anyone who is tackling problems of two stage stochastic programs. It would also be interesting to see whether this could be employed for other bilevel optimization tasks such as those that arise in game theory where the second level task is difficult to solve. Finally, it would be interesting to see if the same approach could work for more stages of decision making. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept