Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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. 
strengths_and_weaknesses: Strengths:
+ The paper is fairly well written and easy to follow.
+ 2SP potentially has practical applications.

Weakness:
- 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.

[1] Learning A Minimax Optimizer: A Pilot Study, ICLR'21.
[2] Learning for Robust Combinatorial Optimization: Algorithm and Application, INFOCOM'22.
[3] Learning to Defend by Learning to Attack, AISTATS'21.
[4] Improved Adversarial Training via Learned Optimizer, ECCV'20.

- 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.

- The single-cut vs. multi-cut tradeoff is only briefly touched without an in-depth analysis.

- Secton 2.2 (Embedding Neural Networks into MIPs) is interesting, but this is taken directly from a prior study.
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.

[1] Learning A Minimax Optimizer: A Pilot Study, ICLR'21.
[2] Learning for Robust Combinatorial Optimization: Algorithm and Application, INFOCOM'22.
[3] Learning to Defend by Learning to Attack, AISTATS'21.
[4] Improved Adversarial Training via Learned Optimizer, ECCV'20.

- 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.

- The single-cut vs. multi-cut tradeoff is only briefly touched without an in-depth analysis.

- Secton 2.2 (Embedding Neural Networks into MIPs) is interesting, but this is taken directly from a prior study.
limitations: NA
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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. 

My concerns with the paper are the following:

1. 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.

2. 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.

Given 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.
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.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
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.

Additionally, the experiments and motivation are sound making this a great contribution to the literature of improving optimization performance with machine learning.

I 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. 

questions: Is it possible to compare against embedding other predictive models in the MIP formulation?

Are there any settings in which the method didn't work, or instance in settings where the first or second stage is highly combinatorial?

Is 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
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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).


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.
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.
* 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.
* 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?
* 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. 
* 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.
review_title: null

Meta-review: metareview: In this paper, the authors proposed to use learning with neural network to amortize the cost in the two-stage optimization problems. The authors tested the algorithms on several problems, demonstrating the advantages of the proposed algorithm empirically. 

Most of the reviewers think this work is interesting, although there are already plenty of existing work considering the similar methods, especially a similar work has been published that using learning to amortize for multi-stage stochastic programming. 

Another concern raised by reviewer is that the empirical comparison is not comprehensive. The decomposition methods, e.g., Benders-based methods, are not involved, which is a major algorithm for two-stage stochastic optimization problems. Therefore, the advantages of the proposed method is not clear. 

Please take the reviewers' points into account to improve the paper. 
confidence: Certain
Decision: Accept