Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper aims to use deep-learning towards solving generic stochastic integer programs. The proposed approach involves using a conditional VAE to model the distribution over scenarios, and leveraging the scenario's latent space embeddings to enable better representative scenario selection: the embeddings are used as inputs to a standard clustering algorithm that returns representatives.

The paper demonstrates that using VAE embeddings improves performance when compared to using the same clustering algorithm on the raw scenario representations. It further demonstrates that using embeddings concatenated with a predicted objective generally improves performance over using the embeddings alone. Finally, the paper shows improvement over two recent approaches.
main_review: Pros:
* Since the distance in VAE embedding space is expected to reflect the problem domain better than the distance in the input space, the use of the VAE for clustering scenarios is reasonable.
* The paper shows improved performance over 2 recent baselines. While the performance falls short of the CPLEX solver, the proposed approach is generally faster.
* The paper also includes a visualization of the latent space colored by objective prediction scores to motivate the concatenation of the predicted objective to the embeddings towards clustering.

Limitations:
* Technical significance and novelty: The paper contributions are primarily empirical. The conditional VAEs usage is pretty standard - to provide better embeddings for clustering; the paper builds encoder / decoder architectures that are specific to the task using standard building blocks (graph CNNs).
* Given the empirical nature of the paper, I think the paper can be improved with more intuition about what the VAE learns and why it improves over distance alone in this application. The objective prediction visualizations address this to some extent, but this only illustrates why the predicted objective is useful, and one could in principle append this prediction to the raw scenario representation as well. It would also be interesting to know how good are the samples from the VAE, whether one could (successfully) use VAE samples instead/in addition to selected samples from the original set, etc.

Clarity:
* The paper is generally clear and the context is explained well, but the writing can be improved in various places (e.g. missing determinant in "encoder for inference process and a decoder for generation process", "In future").

**Updated after rebuttal**

I think the authors have addressed the concerns I have raised and I have increased my score.
summary_of_the_review: The paper demonstrates the use of a conditional VAE in the context of solving stochastic integer programs. The approach seems technically sound and the empirical results show improved performance over both clustering the raw scenarios and over recent baselines. On the other hand (conditional) VAEs have already been used for similar combinatorial optimization tasks before, and their use here towards scenario clustering has small additional significance and novelty.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: Solving stochastic integer programs in practice can be difficult for large problems with many scenarios (i.e., sample discretizations of the uncertain distribution), motivating relevant problems such as scenario reduction and objective prediction. This paper explores these problems by using a graph conditional VAE to learn low-dimensional representations of scenarios and perform downstream tasks in this space. The results show improvements over existing scenario reduction and objective prediction methods over the original high-dimensional space.

main_review: AFTER REBUTTAL:

I thank the authors for providing a detailed rebuttal with several additional experiments. 

In my opinion, this is a nice paper. The technical novelty w.r.t. the ML community seems a bit limited, however, the empirical results (in particular for K=20) are very strong, showing that the proposed method can lead to  high quality solutions (< 20% optimality gap) while reducing an optimization solver's runtime by several orders of magnitude. I would like to see the paper accepted and have raised my score accordingly.


----------------

The paper is well written with a smooth introduction to SIPs and the related literature towards machine learning for integer programming. Furthermore the numerical results shown are impressive and may suggest tremendous advantage over current methods in scenario decomposition. 

I have two major concerns:

1. GVAEs are *very* well studied (e.g., [1]), and a quick search shows there are prior works that explore graph CVAEs (e.g., [2]). However, none of this related literature is discussed, so the placement of this work within the broader GCN literature is unclear and requires further discussion. Further, is there any specific contribution to the GCN literature, or is the proposed method strictly an application of GCNs to a new problem? 


2. The numerical results suggest that the proposed method of using k-medoids in a lower dimensional latent space has tremendous advantages over classical k-medoids and sometimes attains $2x$ improvements. However, in some cases (especially for FLP in Table 3 and 4), all of the methods (including the proposed one) generate very poor solutions with $>100%$ optimality gap. For example with the FLPs in Table 4, it would not be practical to use any of the listed scenario reduction techniques if the nominal problem takes only 2-11 minutes and the scenario reduced solutions are so sub-optimal. I expect that we would require more scenarios and I observe  that the appendix includes some results with a more reasonable setting (e.g., Fig 2) with larger $K$. It would be useful to bring those results to the main text. Furthermore, I believe it would be important to expand the tables in the main text to larger $K$ where the conventional scenario reduction baseline (k-medoids) is meaningful. Otherwise, I would be interested to seeing a comparison with more powerful methods from the scenario reduction literature (e.g., [3]), where $K \leq 10$ is justified.


[1] Kipf & Welling, Variational Graph Auto-Encoders (2016)

[2] Chai, Liu, Duffy, & Kim, Learning to Synthesize Cortical Morphological Changes using Graph Conditional Variational Autoencoder (2021)

[3] Rujeerapaiboon, Schindler, Kuh, & Wiesemann, Scenario Reduction Revisted: Fundamental limits and guarantees (2018) 



summary_of_the_review: The improvement over baselines are nice and the paper is well written, but its positioning within the broader literature and the meaningfulness of the numerical results leave fundamental questions that I would like to see answered before improving the score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of generating representative scenarios for two-stage stochastic integer programmings in which the parameters could be either static (referred to as context) or stochastic (forming a space of scenarios). The proposed method leverages conditional variational autoencoder to learn the distribution of scenarios conditioned on the context, where the encoder computes the latent variables (based on the context and scenarios) while the decoder recovers the scenarios. In particular, the functions are parametrized by graph neural networks and multilayer perceptron. Experiments on two concrete problems are performed. 
main_review: $\textbf{Strengths}$ 
-	This paper tackles a challenging problem. It is significant if one can reduce the number of scenarios required for obtaining a high-quality approximation 
-	Using CVAE for generating effective scenarios is an interesting idea. 
-	The paper provides detailed experimental settings, which are very helpful.

$\textbf{Weaknesses}$ 

I have the following questions to which I wish the author could respond in the rebuttal. If I missed something in the paper, I would appreciate it if the authors could point them out.

Main concerns:
-	In my understanding, the best scenarios are those generated from the true distribution P (over the scenarios), and therefore, the CVAE essentially attempts to approximate the true distribution P. In such a sense, if the true distribution P is independent of the context (which is the case in the experiments in this paper), I do not see the rationale for having the scenarios conditioned on the context, which in theory does not provide any statistical evidence. Therefore, the rationale behind CVAE-SIP is not clear to me. If the goal is not to approximate P but to solve the optimization problem, then having the objective values involved as a predicting goal is reasonable; in this case, having the context involved is justified because they can have an impact on the optimization results. Thus, CVAE-SIPA to me is a valid method. 
-	While reducing the scenarios from 200 to 10 is promising, the quality of optimization has decreased a little bit. On the other hand, in Figure 2, using K-medoids with K=20 can perfectly recover the original value, which suggests that K-medoids is a decent solution and complex learning methods are not necessary for the considered settings. In addition, I am also wondering the performance under the setting that the 200 scenarios (or random scenarios of a certain number from the true distributions) are directly used as the input of CPLEX. In addition, to justify the performance, it is necessary to provide information about robustness as well as to identify the case where simple methods are not satisfactory (such as larger graphs). 

Minor concerns:
-	Given the structure of the proposed CVAE, the generation process takes the input of $z$ and $c$ where $z$ is derived from $w$. This suggests that the proposed method requires us to know a collection of scenarios from the true distribution. If this is the case, it would be better to have a clear problem statement in Sec 3. Based on such understanding, I am wondering about the process of generating scenarios used for getting K representatives - it would be great if codes like Alg 1 was provided. 
-	I would assume that the performance is closely related to the number of scenarios used for training, and therefore, it is interesting to examine the performance with different numbers of scenarios (which is fixed as 200 in the paper). 
-	The structure of the encoder is not clear to me. The notation q_{\phi} is used to denote two different functions q(z|w,D) and $q(c,D)$. Does that mean they are the same network?
-	It would be better to experimentally justify the choice of the dimension of c and z.
-	It looks to me that the proposed methods are designed for graph-based problems, while two-stage integer programming does not have to be graph problems in general. If this is the case, it would be better to clearly indicate the scope of the considered problem. Before reaching Sec 4.2, I was thinking that the paper could address general settings.
-	The paper introduces CVAE-SIP and CVAE-SIPA in Sec 5 -- after discussing the training methods, so I am wondering if they follow the same training scheme. In particular, it is not clear to me by saying “append objective values to the representations” at the beginning of Sec 5. 
-	The approximation error is defined as the gap between the objective values, which is somehow ambiguous unless one has seen the values in the table. It would be better to provide a mathematical characterization. 

summary_of_the_review: This paper considers an interesting problem, but I am not convinced that the proposed models are warranted in theory. In addition, the practical utility is not significant or clear with the presented experiments, and there are many settings needing justifications. However, I look forward to the authors’ response.
review_title: null

Meta-review: This paper presents a conditional variational autoencoder (CVAE) approach to solve an instance of stochastic integer program (SIP) using graph convolutional networks. Experiments show that their method achieves high quality solutions with high performance. 

It holds merit as an interesting novel application of CVAEs to the ML for combinatorial optimization literature, as well as for the nice empirical results which show a very nice improvement. Two reviewers had a concern that the contribution is a bit narrowly focused toward  MILP-focused journal rather than a general-purpose ML conference since the core contribution is the novel application. On the other hand, they believe that combinatorial optimization has received growing interest from the ML community in recent years. 

All three reviewers vote for borderline accept of this paper. The authors have addressed some of reviewers' concerns, hence some reviewers increased their scores throughout the discussion phase.
Decision: Accept (Poster)