Learning Scenario Representation for Solving Two-stage Stochastic Integer Programs
Authors: Yaoxin Wu
Wen Song
Zhiguang Cao
Jie Zhang
Venue: ICLR 2022 Poster (2022)
Keywords: Conditional Variational Autoencoder
Stochastic Integer Programming
Scenario Reduction

Abstract: Many practical combinatorial optimization problems under uncertainty can be modeled as stochastic integer programs (SIPs), which are extremely challenging to solve due to the high complexity. To solve two-stage SIPs efficiently, we propose a conditional variational autoencoder (CVAE) based method to learn scenario representation for a class of SIP instances. Specifically, we design a graph convolutional network based encoder to embed each scenario with the deterministic part of its instance (i.e. context) into a low-dimensional latent space, from which a decoder reconstructs the scenario from its latent representation conditioned on the context. Such a design effectively captures the dependencies of the scenarios on their corresponding instances. We apply the trained encoder to two tasks in typical SIP solving, i.e. scenario reduction and objective prediction. Experiments on two SIP problems show that the learned latent representation significantly boosts the solving performance to attain high-quality solutions in short computational time, and generalizes fairly well to problems of larger sizes or with more scenarios.

Published as a conference paper at ICLR 2022
LEARNING SCENARIO REPRESENTATION FOR SOLV- ING TWO-STAGE STOCHASTIC INTEGER PROGRAMS
Yaoxin Wu',, Wen Zhiguang Cao Jie Zhang'
"School of Computer Science and Engineering, Nanyang Technological University, Singapore Institute of Marine Science and Technology, Shandong University, Qingdao, China
"Singapore Institute of Manufacturing Technology, A A*STAR, Singapore (wuyaoxin, zhangj @ntu. edu. sg; wensong@ema i sdu edu. cn
ABSTRACT
Many practical combinatorial optimization problems under uncertainty can be modeled as stochastic integer programs (SIPs), which are extremely challenging to solve due to the high complexity. To solve two-stage SIPs efficiently, we pro- pose conditional variational autoencoder (CVAE) based method to learn scenario representation for a class of SIP instances. Specifically, we design a graph con- volutional network based encoder to embed each scenario with the deterministic part of its instance (i.e. context) into a cow-dimensional latent space, from which a decoder reconstructs the scenario from its latent representation conditioned the context. Such a design effectively captures the dependencies of the scenarios on their corresponding instances. We apply the trained encoder to two tasks in typi- cal SIP solving, i.c. scenario reduction and objective prediction. Experiments on two graph-based SIPs show that the learned representation signiticantly boosts the solving performance to attain high-qualit, solutions in short computational time, and generalizes fairly well to problems of larger sizes or with more scenarios.
INTRODUCTION
Stochastic integer programs (SIPs) are a class of combinatorial optimization problems (COPs) with uncertain parameters. They focus on finding a best decision for practical task to optimize both the deterministic cost and the expectation of stochastic costs on a set of potential scenarios. Since the uncertain elements commonly exist reality, SIPs are widely applied and studied many fields such as transportation, inventory management, energy optimization, and so on (Jammeli et al. 2019 Dillon et al., 2017) Bruno et al.) [0166] Wallace & Ziembal (005). However, optimally solving SIP intractable especially when many scenarios are involved, due to the fact that: 1) most integer programs themselves are already NP-hard: 2) considerable (even continuous) scenarios significantly increase the computational complexity (Klein| 2021). In reality, solving coddraaeesszed problems may require prohibitively long time. Thus efficient and high-quality approximate solutions for SIPs often practically pursued.
The advances in deep (reinforcement) learning has aroused extensive studies on solving optimization problems with neural networks. The related works have shown promising results in tackling some classic COPs, e.g., vehicle routing, job shop scheduling, combinatorial auction, etc. (Kool et al.
2019 Zhang al., 22200] Lee et al. [220 K Kwon al. 2020 Gasse al., 2019 Chen & Tian 2019 Ichter et al. 2018 Hottung et al. 2000 Wu et al. 2021). However, most of the existing deep learning based methods only focus on deterministic problems, which could hinder their practical applications in the uncertain situation. On the other hand, few carly attempts introduce deep learning to solve
SIPs (Larsen al. 2018 Abbasi et al., 2020 Joe & Lau 2020) [Bengio et al., 2020 Nair et al.) 2018). However, they are generally designed for only specific problems and also lack the ability of generalizing across different problem sizes.
In this paper, we focus on graph-based SIPs, which is a general class of problems with broad ap- plications. We propose to learn the deep latent representation of scenarios in SIPs, which can be
"Equal contribution.
I "oorrsponniig author (zh 1uaaggcao@out1ook look.com

---

Published as a conference paper at ICLR 2022
applied to various downstream tasks in solving SIPs, e.g., scenario reduction and objective predic- tion. Based on the basic two-stage form of SIPs, we leverage conditional variational autoencoder (CVAE) to learn latent and continuous representations of stochastic scenarios while considering the deterministic part of a SIP instance, which we term the context. Specifically, we employ a graph convolutional network (GCN) to learn embeddings of each deterministic integer program, which models the first-stage problem with a single scenario. The learned embeddings are mapped into continuous representations, and then decoded back into corresponding scenarios given the embed- ding of the context. This design ensures that the learned representations of scenarios are correctly linked to the corresponding instances.
The resulting latent space well represents scenarios in class of SIP instances, and we demonstrate its power with two tasks commonly used in solving SIPs. First, we leverage for scenario reduction by finding representative scenarios via an off-the-shelf clustering algorithm, which decreases the problem complexity and meanwhile attains high-quality approximate solutions. Second, we further extend the encoder with an additional sub-network to predict objective values for each scenario. Due to the generalization in the latent continuous space, we readily deploy the prediction task in semi- supervised manner with small number of target objective values. In doing so, the latent space is augmented with the predicted objective value and hence yields more representative scenarios, which further shrinks the approximation gap to the optimal solutions of the original STPs.
In summary, this paper aims to learn scenario representation for solving graph-based two-stage SIPs. The main contributions are follows:
We firstly present deep generative framework to learn representations for scenarios in graph- based two-stage SIPs. It considers dependencies of the scenarios on the deterministic context of each instance, and hence well differentiates scenarios in the latent space.
We apply the learned representations to scenario reduction and objective prediction for SIPs. The representative scenarios derived from clustering of the representations can be used to efficiently compute high-quality solutions for SIPs. Moreover, we further shrink the approximation error by predicting objective values of scenarios via semi-supervised learning.
We evaluate the proposed method on two SIP problems, i.e., the network design problem and facility location problem. Experimental results verify the superiority of the learned scenario rep- resentation for solving SIPs. Our method significantly outperforms existing deep learning based baselines. Notably, also generalizes well to problems with larger sizes or more scenarios.
RELATED WORK
Learning based methods for SIPs. Recent works of deep learning for COPs mostly address de- terministic problems, with scarce attention to uncertainty that commonly exist in practice. Though a few methods apply deep learning to improve approximate solutions for two-stage SIPs, they are mostly designed for some specific problems. Nair al. (2018) train a bit-flipping policy with inforcement learning to improve solutions iteratively, but it is limited to binary decision variables and assumes no constraints in the first-stage problem. Larsen al. (2088) predict properties of op- timal solutions to integer programs (i.e. the first-stage problem with respective single scenario) in a supervised manner. This method is only applicable when operational solutions are not needed. In contrast, Abbasi et al. (2020) predict values of decision variables for blood transshipment problem with fixed-sized instances. To reduce the complexity of SIPs, [Bengio et al. (2020) aim yield one scenario for the first-stage problem, so that the derived solution achieves a small objective value when evaluated with the original set of scenarios. This method assumes complete recourse, with any generated scenario being feasible for the second-stage problem. All the above methods attempt to reduce the expected cost of stochastic scenarios but their applications are limited by distinct as- sumptions or fixed problem sizes. In contrast, method can be used for more general two-stage SIPs, and generalizes well to varying problem sizes or scenario quantities.
Scenario reduction for SIPs. In the SIP formulation, set of scenarios is used to model stochastic events on top of the first-stage problem. It introduces extra complexity which may exponentially increase with its cardinality, owing to the combinatorial search space (Dyer & Stougie 2006). Since the direct optimization with massive scenarios is intractable, the scenario reduction is often con- ducted to find subset of scenarios that well replaces the original set with small approximation
2

---

Published as a conference paper at ICLR 2022
error. Existing reduction methods mainly branches into distribution-oriented and rrreeem-oriented paradigms. The former ones pursue a group of scenarios that closely estimate the probability distri- bution under the scenario space (Henrion & Römisch 2017). The distance between the estimated and actual probability are often measured by Wasserstein distance (Rujeerapaiboon et al. 2018), polyhedral discrepancy (Henrion et al. 2008) or difference of moments (Høyland al. 2003)
These methods neglect the influence of the context on the objective function, c.g., similar scenario distributions may cause different expected costs in disparate SIP instances. Thus, there is re- cent trend towards the study of mooblem-orientee methods (Henrion & Römisch 2018 Fairbrother al., 2019| Keutchayan et al. 2020; 202I), which attempts involve mooblem-specite properties in scenario reduction. For example, Keutchayan et al. (202T) propose to find K scenarios with their objective values separately approximating the expected objective values in the K scenario subsets. Most the above methods are mainly for theoretical proof on stochastic programs (without the restric- tion of integers). In contrast, we firstly propose a deep learning method for SIPs to learn scenario representation, which can be used for both scenario reduction and objective prediction.
3 PRELIMINARIES
3.1 TWO-STAGE STOCHASTIC INTEGER PROGRAMS
As an optimization problem, SIP is usually characterized by both the uncertain parameters that potentially follow certain probability distributions and the discrete solution space due the integer restrictions, It is commonly described by a two-stage formulation as below:
min μ + E (2)
Ax < b, E RR 701
where Q(x, w) == (1. S hos Tux; E x TP²).
In particular, Eq. ①1 and 2 prescribe the first-stage problem with E Th: being the decision
variable, where n1 2 P1: (I. prescribes the second-stage problem, with y IR being the decision variable, where n2 2 P2. We refer to the group of static parameters E R A E mm x and 6 E Ii in the first stage as the context, and assume that the group of uncertain parameters qu IR W. E IR m2 To E Rmmx and ha R follows distribution P. Here focus on SIPs defined on graphs, which are a family of problems with practical applications in many domains such as networks, transportation and scheduling (Rahmaniani al. 2018 An & Lo| 2016).
The primary method to solve the above SIP is sample average approximation (Kleywegt et al,, 2002), which converts it into mixed integer program (MIP) by Monte Carlo simulation and in turn optimizes the following objective:
(()) min a NJx
1 N N Ex,,(r Q(r,w)))
where [w:),n i= a set of scenarios from P, i.e., an independently and identically distributed (i.i.d) random sample of N realizations of uncertain parameters. Typically, a large scenario set is often required to make the distribution of scenarios well P, which may cause intractable MIP for given solver. In this paper, we aim to find small number of informative representatives in {w; ) j= by learning representations of scenarios, which is supposed to considerably boost the computation efficiency with tolerable approximation errors.
3.2 CONDITIONAL VARIATIONAL AUTOENCODER
As an unsupervised generative model, CVAE is developed on top of VAF, and it further controls the data generation process conditioned on additional random variables (Sohn et al. 2015). These conditional variables could be either class labels or certain properties of the data with specific dis- tributions, which are engaged in the input both the encoder and decoder. Optimized with the stochastic gradient variational bayes (SGVB) framework (Kingma & Welling, 2014), the evidence lower bound objective (ELBO) of CVAE on the marginal likelihood for the input data defined as:
log po (X,c) 2 ELBBO X, e) (=1X.)) [lo (X|x,e)) (L),
(4)
3

---

Published as a conference paper at ICLR 2022
where X, c, z denote imput, latent and conditional variables, respectively; both the encoder qs and decoder py are typically parameterized by deep neural networks. Rather than simple distributions of conditional variables in most existing works, in this paper we exploit CVAE to learn scenario representation in SIPs, with conditional variables derived from continuous parameters in the context. For more details of CVAE, we refer readers (Kingma et al. 2014 Feng et al. 2021).
METHODOLOGY
Given a class of SIP instances {-m with parameters drawn from a distribution D, we regard each instance as 2-tuple Xm = (Dm: {wi, in fimi), where Dm denotes the context (i.e. the group of static parameters) in the m-th instance, and wm denotes the i-th scenario (i.e. the i-th realization of uncertain parameters) in the with instance. We aim to learn latent representations (variables) W of scenarios (wm L.V. under the context Dm in each instance.
(=m i=
4.1
CVAE FOR SCENARIO REPRESENTATION
Our CVAE comprises encoder for the inference process and a decoder for the generation process, which are parameterized by deep neural networks &s and pa. respectively. In the generation process, the decoder approximates the posterior distribution of uncertain parameters in scenarios, given the latent and conditional variables, such that:
(5) where f and denote likelihood functions (c.g. Gaussian or multinomial distributions) that are instantiated by po and la. respectively. Note that do not take the raw context D,,. condi- tional variables for the decoder since they are continuous and high-dimensional. It may not only intensify the computational complexity but also overwhelm the latent variable which is typically low-dimensional. In contrast, we leverage the graph neural network (GNN) in the encoder to derive low-dimensional conditional variable Cm from D, Further by preserving the marginal inde- pendence between latent and conditional variables, the decoder will more effectively govern the generation of w'n according to the context Dm (Kingma et al. 2014).
(win Fi: Cm) f(wmm z Cm, 0); (cm Dm) h(Cm; Dm,
In the inference process, the encoder approximates the posterior distribution of latent representations (variables) of scenarios given (wi,. Dm). which is expressed as:
(= wwm Dm) = (2 (no D..). o (u Dm)),
(6)
where we assume a Gaussian distribution of scenario representations with μég and o being param- eterized by neural networks, respectively. As aforementioned, we exploit GNN in the encoder to embed the continuous and high- digen-immnsional wit and Dm, which is also used by the decoder to embed the sole Dm This parameter sharing design contributes to fast learning of embeddings for deriving the latent and conditional variables, i.e., z/m and Cm- To learn disentangled representations for these two types of variables, we force the conditional independence
(Fim Cr win Dm..) (=' (=m/w/m Dm) (Cmllm))
In summary, our CVAE hinges on two important steps, i.c., 1) we first use the encoder to attain scenario representations with respect to the context in each SIP instance; 2) we then use the decoder to reconstruct the scenarios from the latent space according to the context.
Semi-supervised CVAE. With the inferred scenario representations, we can directly conduct vari- ous downstream tasks for solving SIPs, such as scenario reduction using off-the-shelf clustering algorithm. However, may ignore the relationship between scenarios and objective values, which is nontrivial since even similar scenarios would deliver different solutions. Therefore, we also extend CVAE to predict the objective function in a semi-supervised manner. Given that the scenarios are embedded into continuous space by the encoder, the prediction is supposed to be well general- ized Hoamez-Bombbrelll et al. 2018).
Most CVAE models for semi- semi-supervised learning predict discrete targets and regard the ground truth, e.g., class labels, as conditional variables. In contrast, we predict a continuous property of the data (i.e. the objective value) and directly approximate it through the encoder. To this end,
4

---

Published as a conference paper at ICLR 2022
Festurize the graph with (uen. Dm)
Pm
ML.
Am
Lineer projection
Sample
GCN
Lisear projection
Fealurize the graph with Dm
[0:d"]
of
10: 11
Liner projattion
pm
MLP
Figure CVAE structure for learning scenario representations
CPLEX solver to collect optimal objective values {Y [i=1 of the resulting MIP problems, which are defined by respective scenarios with the context, for only a small volume (1% M) of instances in (Xm ) M We refer to the underlying joint distribution of (w Y D.)) Dy. Then infer the objective values with a sub-network, which processes the GNN embedding of (wi, Dm in the encoder, such that the objective function is parameterized as:
Tw (Y (hm)) = (Y ii v); (hi w Dm) = g( w/n: Dms Ø)
(8)
where hin denotes the GNN embedding that is derived by qa-
4.2 NEURAL NETWORKS
A major challenge to parameterize CVAE for SIPs is how to derive an effective embedding of the context, since high-dimensional and continuous. Moreover, also involved in the input to both the encoder and decoder, and significantly influences the eventual scenario representation. A direct use of multi-layer perceptron (MLP) to process static parameters Dm may fail to leverage the problem structure and cannot generalize across instances of different sizes. To overcome these limits, we exploit a GNN (as aforementioned) to embed the context Dm for attaining conditional variables in the decoder. Meanwhile, apply the same GNN to embed each scenario with its context (w", Dm) for attaining latent representations in the encoder. To this end, we first describe graph.
the context with scenarios
SIP graphs. We define a complete graph G = (V,E), where V = fe1 (e...... ,.) denotes nodes with features V Raxd,; & feguluz, 2% V) denotes edges with features E Raxxd.. We formally represent the features the j-th node as vi, [sL,; di] ([:] means concatenation). In specific, & E w denotes realization of uncertain parameters the j-th node and di E D., denotes static parameters on the j-th node. Similarly, the features on edge Ejk is represented as e = [ ddk), where iik and di denote the parameters from the i-th scenario and the context, respectively. Different from existing works that only consider varying parameters
nodes, e.g., Nazari et al. our graph representation is more generic and could be applied to a broader class of SIPs. Particularly, two examples of the graph representation on the network design problem and facility location problem are introduced in Section 4.4.
On top of the SIP graphs, we can exploit GNN to derive embeddings for either the context D. or varying scenarios with the context, i.c., (w Dm), i i= (1..... N). In our method, we adopt the graph convolutional network (GCN). which a commonly used GNN variant (Kipf Welling 2017 Yao et al. 2019). The architecture of our GCN is similar to the one in Joshi et al. (2019). which was leveraged compute an adjacency matrix for solving the travelling salesman problem. Specifically, extend it for graph-based SIP problems to attain graph embeddings for D and (wi,, Dm), denoted as hm and hi. respectively. Detailed structure of the GCN is described in Appendix Next, will revisit our CVAE given the graph embeddings above.
The encoder processes the graph embedding hi with two separate linear projections to compute 2-dimensional vectors of means and standard deviations for latent variables, respectively, ie., M (w",, i Dm)) and a (w Dm) in Eq. (6). Also, we linearly project the graph embedding h.m into a 2-dimensional vector, i.e., Gr. in Eq.
Encoder.
5

---

Published as a conference paper at ICLR 2022
Decoder. We concatenate Cm with the latent variables 2/n and pass them through an MLP to recon- struct the scenario. The MLP is structured by two hidden layers with ReLU activation functions, which are of 128 and 256 dimensions, respectively.
Semi-supervised learning. To echo the semi-supervised CVAE in Section 4.1 we leverage another MLP sub-network process kn It comprises a 51 1--dimensional hidden layer with ReLU activation function, and outputs a single value to estimate the objective value Y
The basic structure of neural networks is illustrated in Figure where ai, and Y are the recon- struction and predicted objective value for the i-th scenario, respectively. Note that we pad uncertain parameters wht with O to embed the sole context (in the lower grey square). In this way, the GCN could be shared to attain both graph embeddings hm and hmn.
4.3 TRAINING INFERENCE
Algorithm 1 Training procedure
Input:
encoder Ps. decader Qú. num. of epochs E, batch size
The training objective is to minimize three loss functions. The first one is defined by the mean square error (MSE) between the reconstructed
1: Initialize parameters ((9) and (f for epoch = 1, 2.... E do Shuflle
2:
3:
DD Dy:
scenarios from decoder and the original ones. It
4:
1, 1,2,--. -.. [P]]
is essentially employed in CVAE maximize the marginal likelihood of the data. The second loss defined by Bullback-Leiblee from the latent variables to the prior Gaussian
5: Retrieve a hatch instances from D2;
6:
Get random sccnario in each instance; Compute ELBBO Eq. 19) f. Adam,A, VZ d)); if objective prediction is trained then
divergence
10:
Retrieve batch instances from Dy:
distribution p(z) (= f). which used
11:
Compute MSE of objectives in Eq. d. + Adam (b, v. VL *)
9
for regularization. The third loss is defined by the MSE between the predicted objective values
12:
13:
end if
14:
end for
and their ground truth. Formally, the objective for training our CVAE is expressed as:
15:
end
[(0, d, ) = Eo(-EEBO(XX.) - a EDy D (Y [n)),,
where (LBO((m)) = F (* lwt. .D..) flog po (wi 2 Cm - KL (wm Dm) Ip(=] involves the first MSE and KI. divergence; and are hyperparameters to balance the three losses. Following the typical training paradigm for VAE, we jointly optimize 0 and Φ via reparameterization trick and Monte Carlo approximation (Kingma Welling 2014). The training procedure is summarized in
Algorithm D where we use the Adam optimizer to update the parameters (Kingma & Ba 2015).
As shown Algorithm we randomly pick one scenario for each instance so that we can process it with its context in a batch. The resulting generalization across both the contexts and scenarios of different instances will allow for a fast training of neural networks. However, the inference we employ the trained encoder to attain the latent representations, by processing all scenarios from set of instances in parallel. It is realized by duplicating the context in each instance for all its scenarios. In doing so, the computational efficiency will be considerably improved for solving the instance with a large cardinality of scenarios, and thus a large amount of instances. For each instance, the derived scenario representations from the encoder are then used for clustering to attain few centers that correspond to representatives among original scenarios, so we end with reduced scenarios.
4.4 APPLICATIONS
We apply our method to learn scenario rep- resentation in two typical SIP problems, i.e. the network design problem (NDP) and facil- ity location problem (FLP) (Keutchayan et al.] 202T]. We represent them as the SIP graphs, whose features on nodes and edges including both static and uncertain parameters are listed in Table [ For FLP, the parameters tokenized by F. and C. mean that they are peculiar to fa- cility and customer nodes, respectively. More details about the two problems and their param- eters can be found in Appendix and
Table 1: Features on SIP graphs of NDP and FLP
Feats
Types Parameters
Digits
SPP
demand
opening cost, transporiation cost, capucity
3
f
None
0
coordinats, opening cost (F), capacity (F)
2(4)
presence (C.)
dyb
distance between nodes

---

Published as a conference paper at ICLR 2022
5 EXPERIMENTS
We evaluate our method on NDP and FL.P to demonstrate its effectiveness. On the one hand, we train the CVAE to only learn representations for scenarios (Line 5~8 in Algorithm[]) and the trained encoder can attain representations in each instance, which are directly used for scenario reduction by finding representatives via an off- she-the--selff clustering algorithm. On the other hand, we train the remi-supervised CVAE to simultaneously learn scenario representations and predict objective values (Line 5~13). After the training, the neural network attain representations and objective values for each scenario and we concatenate them for clustering to find more informative scenarios as representatives. We refer to the above two paradigms as CVAE-SIP and CVAE-SIPA, respectively. In the following experiments, we compare them with other learning based methods, and assess their generalization performance across problems with varying sizes and scenario cardinalities.
5.1 SETUP
Instance generation. Our instances are generated following the way in (Keutchayan et al. 2021 Specifically, we generate NDP instances with 14 nodes including 2 source nodes, 2 target nodes and 10 transition nodes. For FLP, we designate 10 facility nodes and 20 customer nodes. We generate 200 scenarios for each instance both problems. To evaluate the generalization performance, we generate larger instances by doubling and quadrupling the number of transition nodes for NDP, respectively. We do the same to both facility and customer nodes for FLP. Besides, we also double and quadruple the scenario cardinality in both problems. More details are provided in Appendix D
Training. We collect 12, 800 instances (of normal size) for NDP and FLP, respectively, and normal- ize each type of parameters into [0, 1] across instances. Regarding CVAE-SIP, train model without the sub-network (used for the prediction task) by solely optimizing the ELBO loss in Eq. D). Regarding CVAE-SIP, we train neural networks for learning representation and objective pre- diction simultaneously. as shown in Algorithm| T We set hyperparameters 3 = 0.005 and a = 100 in Eq. (9). For both problems, CVAE-SIP and CVAE-SIPA are trained with 100 and 400 epochs, respectively. The batch size and learning rate are set to 128 and 10-4, We run the training on a server using single GeForce RTX 2080 Ti GPU.
Testing. Pertaining to CVAE-SIP, we employ the K-medoids algorithm (Park & Jun 2009 to obtain representative scenarios based on the latent representations. We keep its default settings and only change the number of clusters (i.e. K). Given the attained K representatives, we can derive the approximation solution by reformulating Eq. (3) as:
Ō(x) = min / A
N
E ((r,))) N
(10)
where us means the representative from the k-th cluster and the number of intra-cluster population equals to Nr. Accordingly, the approximation error is defined as the garß between objective values of the approximate solution derived from Eq. (10) and the optimal solution from Eq. (3). Pertaining to CVAE-SIPA, we infer both the latent representations and objective values of scenarios, which are concatenated as augmented representations to attain the representatives. To reduce the influence by the potential concurrent processes, we conduct the evaluation different desktop computer, which uses a single Nvidia Quadro P4000 GPU with a Xeon W-2133 CPU@: 3.66 GHz.
5.2 COMPARISON ANALYSIS
We compare with four baseline i.e., 1) CPLEX IBM 2017), with default settings to compute optimal solutions. It is also used to solve the approximation problem with representative scenarios. 2) K-medoids, the same clustering algorithm as used in our method. However, we apply it to directly cluster the original scenarios rather than the learned low-dimensional representations. 3) Scenario- M. a supervised method with hand-crafted features predict a scenario for solving a variant of
FLP (Bengio et al., 2222)). 4) Solution-M a supervised method with raw features to predict the first-stage decision variables for solving blood transshipment problem (Abbasi al. 2020).
'In specific, we denote the optimal solutions in Fq. 10 and Fq. by ã and x" respectively. The gap is +).. where assume minimization problems and o 10-10
defined as (0()) - (0===)/((((())
A short comparison with methods in operations research is also given in Appendix
"The training details of Scenario-M and Solution-M are summarized in Appendix

---

Published as a conference paper at ICLR 2022
Table 2: Comparison with baselines
NDP (14:200) 200)
FLP (30; 200)
K=5
K=10
K=20
K=5
K=10
K=20
Method
Obj.
Error
Time
Obj.
Error
Time
Obj-
Error
Time
Obj.
Error
Time
Obj.
Error
Time
Obj.
Earor
Time
CPLEX
635.75
0.00
18s
635.75
0.00
18s
635.75
0.00
18s
236.71
0.00
18s
236.71
0.00
18:
236.71
0.00
18s
Sconario-M
2533.50
2533.50
2533.50
2.96
0.8
1980.05
0.68
1980.03
7.11
1980.03
7.11
0.6s
Solation-M
81
0.26
0.8 798.81
0.8s
798.81
0.26
0.8s
736.21
1.87
0.2s
736.21
1.87
0.2s
736
1.87
0.2s
K-medoids
976.47
0.54
0.36
261.18
0.19
0.65
672.02
0.08
1s 2390.06
9.06
0.2s
1344.39
39
4.57
0.3s
502.68
1.17
CVAE-SIP
930.73
0:48
0.78
734.24
0.15
0.95
637.99
0.02
1s
929.61
2,87
0.78
482
20
0.99
0.75
282.49
0.23
18
CVAE-SIPA
769.70
0.24
0.68
687.68
0,08
0.8s
642.12
0.03
Is 709.08
1.71
0.68
381.41 0.58
0.7s
264.01
0.15
(n; N) means nodes and N scenarios; Bold means the best result from the learning based methods.
Table 3: Generalization to large-scale problems
NDP (24; 200)
FLP 200)
K=5
K=10
K=20
K=5
K=10
K=20
Method
Obj
Frror
Time
Ohj
Error Time
Obj.
Emor
Time
Obj
Error
Time
Obj
Froor
Time
Ohj
Error Time
CPLEX
602.47
0.00
2m
602.47
0.00
2m
602.47
0.00
2m
335,37
0.00
11m
335.37
0,00
11m 335,37
0,00 11m
Socnarie-M
2238.63
2,68
2s
2238.63
2.68
2238.63
2,68
2s
Solution M
K-medoids
981.94
0.63
723.62
662.46
3549.25
9.72
1549.53
3.74
561.97
CVAE-SIP
871.73
0.45
2s
696.22
0.16
659,92
0.09
4s
1083.12
2.17
3s
748.59
1,21
5s
506.75
0.57
CVAE-SPA
809.65
0.34
2s
637.72
0.06
610.58
0.01
56
974.17
1.86
3x
746.02
1.18
5s
470.39
0.44
8s
NDP (44; 200)
FLP (120: 200)
K=5
K=10
K=20
K=5
K=10
K=20
Method
Obj
Error
Time
Obj.
Error
Time
Obj.
Emor
Time
Obj.
Urror
Time
Obj
Erro
Time
Obj.
Eroor Time
CPLEX
580.67
0.00
23m
580.67
0.00
580.67
23m
484.60
0.00
484.60
0.00
484.60
0.00
Scenario-M
2163.74
2.77
2163.74
2163.74
Solution-M
K-medoids
803.99
0.38
3s
652.78
0.12
76
595.15
0.04
14s
6675
13 12.56
6s
2803.77
4.86
21s
1183.44 44
1.56
61s
SIP 1079.80
0.84
56
615.99
0,06
8s
588.18
0.02
16s
1585.53
2.27
12s
985.45
0.99
35s
627.30
0.28
5ts
CVAE-SIPA 682.35 0.17
627.62
0.08
581,07
0,00
17s
2051.45
3.13
16s
910.50
0.84
33s
594.33
0.22
6%
We evaluate all methods on 200 instances of normal size for NDP and FLP, respectively. We set K = 5, 10. 20 in K K-medoids for both problems so that we could access the performance against the number of representatives. Note that the computation by CPLEX, Scenario-M and Solution-M is independent of K. The results are displayed in Table 2 where we record the average of objective values, approximation errors and computational time over all instances, respectively. As shown, both CVAE-SIP and CVAE-SIPA consistently outperform K K-medoids in all cases. Though K K-medoodd can also improve the solution quality as K grows, our methods efficiently attain solutions with much smaller errors. It implies that we achieve more informative representatives with the learned low-dimensional representations, which help deliver high-qualig solutions. On the other hand, our methods significantly outperform Scenario-M and Solution-M for the three respective values of K. This suggests that the representatives found by our methods are able to approximate the original problem more accurately than the approximation with the single scenario or solution. Furthermore, we observe that CVAE-SIPA is generally superior to CVAE-SIL SIP, which indicates that the predicted objective values could effectively enrich the scenario representations for achieving more informative representatives and thus better solutions. Last but not least, all the learning based methods consume fairly short time compared to the sole CPLEX.
5.3 GENERALIZATION ACROSS PROBLEM SIZES
A desirable generalization to larger problems is necessary for learning based methods. To verify such ability of our methods, we apply the previously trained networks directly infer another 50 larger instances (of two levels) for both NDP and FLP, respectively. The instances are generated following the operation of doubling and quadrupling described in Section 5.1] The basclines are also directly applied to these larger instances except Solution-M since its output dimension (i.e. number of deci- sion variables) is fixed only for the problem of normal size. Similarly, Scenario-M is not applicable to FLP where the scenario dimension (i.e. number of customer nodes) changes with problem sizes. For CPLEX, we set a Ih time limit on FLP (120; 200). In Table 3 the upper and lower half contains the results on doubling and quadrupling instances, respectively. As shown, CVAE-SIP is superior to K --medoids and Scenario-M M in most cases except NDP (44; 200) with K=5. On the other hand, CVAE-SIPA generally achieves the smallest emrors but performs inferior to CVAE-SIP on NDP (44; 200) with 1=10 and FLP (120; 200) with K=5. This might stem from the degenerated accuracy of objective prediction, which induces solutions with relatively large penalties some instances.
8

---

Published as a conference paper at ICLR 2022
Table 4: Generalization large scenario cardinalities
NDP (14; 400)
FLP (30; 400)
K=5
K=10
K=20
K=5
K=10
K=20
Mothod
Obj.
Error
Time
Obj.
Error
Time
Obj.
Error
Time
Obj-
Error
Time
Obj.
Error
Time
Obj.
Error
Time
CPLEX
634.50
0.00
Im
634.50
0.00
1m 634,50
0.00
1m
244.63
0.00
2m
244.63
0.00
2m
244.63
0.00
2m
Seceario-M
2266.88
2.58
2266.88
2.58
2266.88
2.58
5260.62
12.79
5260.62
12.79
5260.62
12.79
Solution-M
791.95
0.26
0.78 791.95
0.26
0.7g
791
0.26
1215.86
0.5g
1215.86
5.37
0.5g
1215.80
0.5s
K-medoids
972.69
0.53
0.3s
730.18
0.15
0.5s
650.45
0.04
1848.21
6.12
0.2s
734 44
2.00
0.4s
497.64
0.92
1s
CVAE-SIP
887.76
0:41
0.8s
711.63
0.12
Is
656.06
0.05
2s
701.73
1.8
1s
468.47
0.86
Is
439.52
0.73
28
CVB--SIPA
881.05
0.38
0.84
676.99
0.06
1s
645.75
0.03
26
723.75
1.89
1s
439.08
0.77
294.02
0.15
28
NDP (14; 800)
FLP (30: 800)
K=5 Error
K=10
K=20 Error
K=5
K=10
K=20
Method
Obj.
Time
Emor
Time
Obj.
Time
Obj-
Emor
Time
Obj.
Emor
Time
Obj-
Emor
Time
CPLEX
633,34
0.00
5m
0.00
5m
0.00
239.45
7m
239.45
0.00
7m
239.45
7m
Scenarin-M
2137.65
2.36
0.76
2137.65
2.36
0.7%
2137.65
2.36
0.7g
3807-41
9.93
2s
3807.41
9.93
2s
3807.41
9.93
2s
Solution-M
815.13
0.28
0.8s
815.13
0.28
0.8s
815.15
0.28
0.8s
1082.62
3.76
0.75
1082
0082.62
3.76
0.7s
1082.65 222
3.76
0.7s
K-msdoids
896.35
0.42
0.38
770.99
0.20
0.78
678.33
0.08
1174,66
4.18
0.24
1091.77
3.34
0.36
732.85
1.72
1s
CVAE-STP
900.59
0.42
658.40
0.03
74
0.09
600.28
1.36
2s
351.18
0.49
308.24
0.23
2s
CVAE-SUPA
990.76
420.95
0.77
296.98
Notably, the computational time by CPLEX rises drastically on larger problems, in comparison with those in Table Such low efficiency might not be acceptable in practice, especially where real-time decisions are required for handling number of problem instances simultaneously. In contrast, our methods deliver solutions with small penalties short runtime. In Appendix [F] we draw curves of the average error against the number of representative scenarios used in FLP problems.
5.4 GENERALIZATION ACROSS SCENARIO CARDINALITIES
From a practical view, the cardinality of scenarios in SIP problems might be changed due certain reasons, e.g., new observations are added or outdated ones are removed (Issac & Campbell 2017). Therefore, a learning based method for SIPs should be able handle this varying dimension via generalization. To this end, we evaluate our methods and baselines on 50 instances of NDP and FLP with doubling and quadrupling scenarios, respectively. The results in Table 3 show that our methods can still achieve the smallest errors across most settings, except NDP (14; 400) with K=5, where Solution-M performs better. It implies that our methods are less sensitive to the scenario cardinality. Since our methods process all scenarios in parallel, they solve instances with scenarios up to 800 in about 2 seconds, which is significantly faster than CPLEX. Additionally, we also test with scenarios generated from varying distributions and different dependencies the context. The details are provided in Appendix
5.5 OBJECTIVE PREDICTION
We further demonstrate the efficacy of the semi-supervised learning for objective prediction. The trained model directly adopted infer objective values of scenarios in NDP and FLP instances. The results are gathered in Figure 3 and 4 which show prediction is fairly accurate for both problems even when generalizing to larger problem sizes or scenario cardinalities. well verifies the effectiveness of our semi-supervised design, which only needs to solve small volume (1%) of training instances. In addition, the sample efficiency is also enhanced through the generalization over the latent space. More details can be found in Appendix H
6 CONCLUSIONS AND FUTURE WORK
In this paper, we present a deep learning method to solve graph-based two-stage SIPs. We lever- age CVAE to learn latent representations of stochastic scenarios conditioned on the context of a SIP instance. With the learned representations, we conduct two downstream tasks for solving SIP, i... scenario reduction and objective prediction. The evaluation on two classic SIP problems has shown that our method is able to find less yet informative representatives for improving both solu- tion quality and computation efficiency. Additional studies also verify that our method can be well generalized to larger problem sizes, larger cardinalities of scenarios and different distributions of scenarios. In the future, we will attempt to automate the decision on the optimal number of repre- sentatives for scenario reduction, and extend method towards solving general two-stage SIPs.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
This research was conducted at Singtel Cognitive and Artificial Intelligence Lab for Enter- prises (SCALE@NTU), which collaboration between Singapore Telecommunications Limited (Singtel) and Nanyang Technological University (NTU) that is supported by A*STAR under its In- dustry Alignment Fund (LOA Award number: E1701. Wen Song supported by the National Natural Science Foundation of China under Grant 62102228, and the Shandong Provincial Natural Science Foundation under Grant RR2202QQF06)
REFERENCES
Babak Abbasi, Toktam Babaci, Zahra Hosseinifard, Kate Smith-Miles, and Maryam Dehghani. Pre- dicting solutions of large-scale optimization problems via machine learning: case study in blood supply chain management. Computers & Operations Research, 119:104941, 2020.
Kun An and Hong K Lo. Two-phase stochastic program for transit network design under demand uncertainty. Transportation Research Part B: Methodological, 84:157-181, 2016.
Yoshua Bengio, Emma Frejinger, Andrea Lodi, Rahul Patel, and Sriram Sankaranarayanan. A learning-based algorithm to quickly compute good primal solutions for stochastic integer pro- grams. In International Conference on Integration of Constraint Programming, Artificial Intelli- gence, and Operations Research, pp. 99-111. Springer, 2020.
Sergio Bruno, Shabbir Ahmed, Alexander Shapiro, and Alexandre Street. Risk neutral and risk averse approaches to multistage renewable investment planning under uncertainty. European Journal of Operational Research, 250(3):979 989, 2016.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion. In the 33rd Conference on Advances in Neural Information Processing Systems (NIPS), pp. 6278 6289, 2019.
Mary Dillon, Fabricio Oliveira, and Babak Abbasi. two-stage stochastic programming model for inventory management in the blood supply chain. International Journal of Production Economics, 187:27 41, 2017.
Martin Dyer and Leen Stougie. Computational complexity of stochastic programming problems. mathematical programming, 106(3):423-432. 2006.
Jamie Fairbrother, Amanda Turner, and Stein W Wallace. Problem-driven scenario generation: an analytical approach for stochastic programs with tail risk measure. Mathematical Programming, pp. 1-42, 2019.
Hao-Zhe Feng, Kezhi Kong, Minghao Chen, Tianye Zhang, Minfeng Zhu, and Wei Chen. Shot-vae: Semi-supervised deep generative models with label-aware elbo approximations. In Proceedings of the 35th Conference on Artificial Intelligence (AAAI), pp. 7413-7421,
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact com- binatorial optimization with graph convolutional neural networks. In Proceedings of the 33rd Conference on Neural Information Processing Systems (NIPS), 2019.
Rafael
Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lobato, Benjamín Sánchez- Lencceiz-enngeingg. Dennis Sheberla, Jorge aguilera-Iparragurre Timothy D Hirzel, Ryan P Adams, and Alán Aspuru-Guzik. Automatic chemical design using data-dríven contin- uous representation of molecules. ACS central science, 4(2):268-276, 2018.
Holger Heitsch and Werner Römisch. Scenario reduction algorithms in stochastic programming. Computational optimization and applicaaions, 24(2):187-206, 2003.
René Henrion and Werner Römisch. Optimal scenario generation and reduction in stochastic pro- gramming. Humboldt-Univen zu Berlin, hww.mmntissshattuuussssssstttiit Fakultät... 2017.
10

---

Published as a conference paper at ICLR 2022
Réne Henrion and Werner Römisch. mroblem-basee optimal scenario generation and reduction in stochastic programming. Mathematical Programming, pp. 1-23, 2018.
René Henrion, Christian Küchler, and Wernrr Römisch. Discrepancy distances and scenario reduc- tion in two-stage stochastic mixed-integer programming. Journal of Industrial Management Optimization, 4(2):363, 2008.
André Hottung. Bhanu Bhandari, and Kevin Tiemny. Learning latent search space for routing problems using variational autoencoders. In the 8th International Conference on Learning Rep- resentations (ICLR), 2020.
Kjetil Høyland, Michal Kaut, and Stein W Wallace. A heuristic for moment-matching scenario generation. Computational optimization and applications, 24(2):169-185, 2003.
IBM(2017). Ibm ilog cplex 12.10 user manual ibm crop. 2017.
Brian Ichter, James Harrison, and Marco Pavone. Learning sampling distributions for robot motion planning. In Proceedings of the International Conference on Robotics and Automation (ICRA), pp. 7087-7094, 2018.
Preethi Issac and Ann Melissa Campbell. Shortest path problem with are failure scenarios. EURO Journal on Transportation and Logistics, 6(2):139-163) 2017.
Haifa Jammeli, Majdi Argoubi, and Hatem Masri. bi-objective stochastic programming model for the household waste collection and transportation problem: case of the city of sousse. Operational Research, pp. 1-27, 2019.
Waldy Joe and Hoong Chuin Lau. Deep reinforcement learning approach to solve dynamic vehicle routing problem with stochastic customers. In Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS), volume 30, pp. 394-402, 2020.
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. In INFORMS Anmual Meeting, 2019.
Julien Keutchayan, David Munger, and Michel Gendreau. On the scenario-tree optimal-value error for stochastic programming problems. Mathematics of Operations Research, 457-51955 2020.
Julien Keutchayan, Janosch Ortmann, and Walter Rei. Problem-driven scenario clustering in stochastic optimization. arXiv preprint arXiv:2106.1 11717, 2021.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In the 3rd International Conference on Learning Representations (ICLR), 2015. 2015.
Diederik P. Kingma and Max Welling, Auto-encoding variational bayes. In the 2nd International Conference on Learning Representations (ICLR), 2014.
Diederik P Kingma, Shakir Mohamed, Danilo Jimenez Rezende, and Max Welling. Semi-supervised learning with deep generative models. In the 28th Conference on Advances in Neural Information Processing Systems (NIPS), pp. 3581-3589, 2014.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In the 5th International Conference Learning Representations (ICLR), 2017.
Kim-Manuel Klein. About the complexity of two-stage stochastic ips. Mathematical Programming, pp. 1-19, 2021.
Anton J Kleywegt, Alexander Shapiro, and Tito Homem-de Mello. The sample average approxima- tion method for stochastic discrete optimization. SIAM Jourmal on Optimization, 12(2):479-502 2002.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, leam to solve routing problems! In the 7th International Conference Learning Representations (ICLR), 2019.
11

---

Published as a conference paper at ICLR 2022
Yeong-Date Boong-Daeean Kwon, Jinho Choo. Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. In the 34th Confer- on Advances in Neural Information Processing Systems (NIPS), 2020.
Eric Larsen, Sébastien Lachapelle, Yoshua Bengio, Emma Frejinger, Simon Lacoste-Julics and An- drea Lodi. Predicting solution summaries to integer linear programs under imperfect information with machine learning. arXiv preprint arXiv:1807.11872 2018.
Mengyuan Lee, Seyyedali Hosseinalipour, Christopher Greg Brinton, Guanding Yu, and Huaiyu Dai. A fast graph neural network-based method for winner determination in multi-unit combina- torial auctions. IEEE Trunsactions on Cloud Computing, 2020.
Vinod Nair, Dj Dvijotham, lain Dunning, and Oriol Vinyals. Learning fast optimizers for contextual stochastic integer programs. In Proceedings of the 34th Conference Uncertainty in Artificial Intelligence (UAI), pp. 591-600, 2018.
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. In the 32nd Conference on Neural Information Processing Systems (NIPS), pp.
2018.
Hac-Sang Park and Chi-Hyuck Jun. A simple and fast algorithm for k-medoids clustering. Expert systems with applications, (6(2):3336-3344) 2009.
Ragheb Rahmaniani, Teodor Gabriel Crainic, Michel Gendreau, and Walter Rei. Accelerating the benders decomposition method: Application to stochastic network design problems. SIAM Jour- nal on Optimization, 28(1):875-903, 2018.
Napat Rujeerapaiboon, Kilian Schindler, Daniel Kuhn, and Wolfram Wiesemann. Scenario reduc- tion revisited: Fundamental limits and guarantees. Mathematical Programming, pp. 1-36, 2018, 8.
Kihyuk Sohn, Honglak Lee, and Xinchen Yan. Learning structured output representation using deep conditional generative models. the 29th Conference on Advances in Neural Information Processing Systems (NIPS), 28:3483-3493 34913,3491,222 2015.
Stein W Wallace and William T Ziemba. Applications stochastic programming. SIAM, 2005.
Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Learning large neighborhood search policy for integer programming. Advances in Neural Information Processing Systems, 34, 2021.
Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text elassification. In Proceedings of the 33rd Conference on Artificial Intelligence (AAAI), pp. 7370-7377, 2019.
Cong Zhang, Wen Song, Zhiguang Cao. Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. In the 34th Conference on Advances in Neural Information Processing Systems (NIPS), volume 33, pp.
2020.
12

---

Published as a conference paper at ICLR 2022
A GRAPH CONVOLUTIONAL NETWORK
Given a complete SIP graph as defined in Section edges by separate linear transformations below:
4.2 we first process the features of nodes and
v = VW. + bbi ED EW + ba
(11)
where E Ruxd, and E Raxaxd, are the raw features (i.e. parameters in Table ! on nodes and edges, respectively; W E Rd.x128 and W x128 are trainable weights with corresponding bias vectors b, E R1x122 and b2 E RIx128_ Note that we also use different linear transformations for heterogeneous nodes edges. For example, the location nodes of facilities and customers processed separately.
Next, we advance the node and edge embeddings by the graph convolution layer for L iterations, and each iteration has its own parameters, which are expressed as:
o(d))) Σx ExaEVo o(ee
v/t2 =v- + FRELLU(B((V)))) +
Σ The o w.)). The =
(12)
1+1 jk ccjx PRELU BN ( W/ vj w v/ w)), 1= --0...,,--I
where W 1...,, W! E 12281128 @ means the element-wise product; a the sigmoid activation function; is small value to avoid numerical error. Initially, the node embedding vÿ is the j-th row of matrix v and edge embedding Ei the element at the j-th row and k-th column of matrix E.. The above graph layer is similar to the one in Joshi al. (2019) except that we use parametric rectified linear unit with its learnable parameter being 0.25.
After (L=10) iterations of the above convolution, the node and edge embeddings are represented as J and (, respectively. We attain the graph embedding by the mean pooling over all the node embeddings. We neglect edge embeddings considering that their information has already been involved in node embeddings, after multiple convolutions.
Parameter sharing The graph embedding network based on Eq. 11 and 112 is able to process the sole context Dm with its static parameters on the graph. Also it can process the context with any scenario in the instance, by featurizing the graph with both static parameters in Dm. and a scenario w To foster the learning efficiency, we use a single network to process these two featurizations. It achieved by padding the uncertain parameters with zeros when we only process the context.
We represent the resulting graph embeddings by hn and him, which are further used to produce conditional and latent variables and meanwhile predict objective values, stated in Section 4.2
B NETWORK DESIGN PROBLEM
Given complete directed graph (V, E), each edge eyk & points from by U2 where Uy E V. We denote the set of source and target nodes as S and T respectively. The features on an edge include its capacity qjk, opening cost Ojk and transportation cost hike for one unit of commodity c C.
Scenarios The uncertainty exists in the demands on each node, In specific, the parameter d',, denotes the demand of commodity e on node v, in the i-th scenario. A penalty f. is given to source node scenario due to the capacity limit of opened edges.
its commodities are not fully transported
Decision variables The decision variable in the first stage is denoted by æyjk- Zik = means that the edge Czk open to transport commodities, otherwise ıyzk = 0. The decision variable the second stage is denoted by Vrkes which means the units of commodity transported along the edge esk in the i-th scenario.
13

---

Published as a conference paper at ICLR 2022
The objective of NDP is to decide the edges to be opened, which minimizes the total opening cost and expected transportation cost (including the penalty). The SIP formulation is expressed as:
N N
min
Σ
oj +
Σ ESEEE
tykeh + E
(13)
1=1 eEC
SES
OSKEE
OSKEE
s.t.
Σ
Vike
Σ
Vike= = d
((. (14)
My
EgREE
Vike
Vike= O,
((AAG) NJ (15)
Ry=1
d
Uike + M Msc
ES N] (16)
81=8
Σ Uymn S 9jkT GEC
N) (17)
Esc, Tikk (0, 1jjk o0).
(18)
where M is a large value which ensures that the source node will not be penalized if all its com- modities are transported.
C FACILITY LOCATION PROBLEM
The facility location problem comprises F and C' locations for facilities and customers, respectively. Each facility location is featured by an opening cost 0y, f {1...., F} and a facility has q units of resources that can be provided to customers. We assume that the number of facilities to be opened not larger than v. For each customer c E {I...., C}. it consumes ger units of resources is served by the facility at the location f, and the induced service cost is denoted by Sef-
Scenarios
The uncertainty exists in the presence of customers. In specific, the parameter hyg refers to the presence of the customer e the i-th scenario, i.e., h = 1 means that the customer e is present to be served in scenario i, otherwise h: = 0. A penalty by is given to the facility f in scenario if one additional unit of resource is needed for it to meet the demand.
Decision variables The decision variable in the first stage is denoted by zy.. xz = means that a facility is open at location ff to provide services, otherwise zy = 0. The second-stage decision variables include v', and z1. In specific, y²r means that the customer e served by facility at location f in the i-th scenario, otherwise Ves = 0. = means the quantity of additional resources required at facility location j' to meet the total demand of its customers, in the i-th scenario.
The objective is decide the locations to build the facilities, cost and the expected service cost including the potential penalty. The two-stage SIP formulation of the facility location problem is expressed as:
to minimize the total opening
min
Σojas oojz FEF
SofVles byzt)
(19)
cEC FEF
JEP
s.t.
ΣΦ1 x E.
(20)
fer
Σ JefVie S q. + 2 CEC
Fx
(21)
2) S MIy;
(l..)
N)
(22)
Ever
Ves =li-.
(c))) N)
(23)
SEF
2y, E 1):1) e (o)
(24)
14

---

Published as a conference paper at ICLR 2022
where M is a large value that constrains 2 to 0 if z/ 0, as ensure that the facility f will not be penalized if it is not open.
D DETAILS OF INSTANCE GENERATION
We generate NDP instances with 14 nodes, in which the commodities two source nodes are trans- ported to another two target nodes to meet their demands. The remaining nodes are only for transi- tion without demands. We set two types of commodities and their quantities uniformly sampled from [5, 15] in each scenario. For each edge, we uniformly sample the opening cost, shipping cost and capacity from [3, 11], [5, 11] and [10, 41], respectively. A penalty 1000 will be triggered for each source node its commodities cannot be fully transported due to the capacity limit of opened edges. For FLP, we consider 10 facility nodes and 20 customer nodes, with their coordinates uniformly sampled from the unit square [0, 1] x [0, 1]. The opening cost and capacity for each facility are uni- formly sampled from [40, 84] and [30, 60). We generate binary values through Bernoulli sampling for customer nodes to indicate their presence in a scenario, with probabilities uniformly sampled from 10.4, 0.6] for each node. penalty 1000 is set for each facility node if it cannot meet one unit of demands. We generate 200 scenarios for each instance of both problems. To test the gen- eralization performance, we generate larger instances by doubling and quadrapling the number of transition nodes for NDP, respectively. We do the same both facility and customer nodes for FLP. Regarding the scenario, we also double and quadruple its cardinality in both problems.
E TRAINING DETAILS FOR THE TWO BASELINES
Scenario-M This method aims to generate one scenario, which can result in a good approximate solution. not easy since for each instance, sufficient scenarios need be evaluated attain the target scenario for supervised learning. To avoid much computational burden, [Bngiio et al. (2020) compute the average of scenarios as the initial one and then iteratively improve solution as the optimal one. However, the improvement heuristic used cannot guarantee that the attained one exists in the original set of scenarios. To tackle this issue, we adapt the method to track the improvement along existing scenarios. Specifically, we find the 20 scenarios nearest to the average and compute the MIPs defined by each of them with the context. We determine the target scenario by picking the with the most similar solution to the optimal one. This method could be used for both NDP and FLP.
derive a similar
We conduct the same featurization as described in Appendix A.4 in (Bengio et al. 2020), and use both linear regression (LR) and artificial neural network (ANN) with MSE loss. In addition, we also the same GCN in our method to directly process we only imput the context with the average of scenarios to GCN, and the graph embedding is linearly projected into output estimate scenarios. The reported results in the main paper are delivered by GCN, which we find outperforms IR and ANN in most cases.
parameters in SIP instances. Specifically,
Solution-M Following (Abbasi al.) 2020), directly predict the first-stage solution in both NDP and FLP. Despite the machine learning algorithms listed in the paper, we use the same GCN in our method for training. It is more powerful process the raw parameters under the graph representation. In our cases, the raw parameters are the static parameters in the context for both NDP and FLP. We take them as the input into GCN and the output dimension is same as the number of first-stage decision variables. If there is no static parameters on nodes or edges, we use 0 for them to run GCN as usual.
For both supervised methods, we use 12,800 instances (of normal size) in the training with the number of epochs 100, batch size 64 and learning rate 0.001. We test them with diverse instances as described in corresponding experiments in the main paper.
F ADDITIONAL RESULTS ON LARGE FLP
We evaluate our methods on FLP of large sizes to show the trend of the average of representative scenarios grows. We follow the experimental setting in Section [3.3] (333annd and apply the trained model to solve 50 instances from FL.P (60; 200) and FLP (120; 200). We set K from 1 to
the number
15

---

Published as a conference paper at ICLR 2022
FLP (60; 200)
(120: 200)
80
k-meddsds CVAE-SIP CVAE-SIPA
K- m-ddddss
CVAE-SIP
CVAE-SIPA
Average g Error
Average Error
30
20
20
10
0
101112 1415 161
1
45
101112131145111 16177111111111
Number of Representatives (K)
Number of Representativess (K)
Figure 2: Errors with different values of K
20 and thus attain solutions with varying numbers of representative scenarios. The curve of aver- age approximation errors is plotted in Figure 2 We observe that both CVAE-SIP and CVAE-SIPA persistently reduce errors towards 0 as K grows. It means that our methods are consistently attain- ing more effective representatives from scenarios, which help deliver better solutions. Meanwhile, CVAE-SIP and CVAE-SIPA outperform K- K-medoids with different K on both problems, especially on FLP (120; 200). It again verifies the merit of the learned representations for solving SIP prob- lems. The comparison between CVAE-SIP and CVAE-SIPA implies that though CVAE-SIPA is superior to CVAE-SIP at the early stage of the curve, i.e., K= .,,, they are on par with each other when more representatives are used eventually.
Table 5: Results on distributions and dependencies
NDP (14; 200); Normal
NDP (14; 200); Binomial
K=3
Kw5 Error
K=10
K=3
K=5
K=10
Method
Obj.
Eror
Time
Obj.
Time
Obj.
Error
Time
Obj
Eroor
Time
Obj.
Error
Time
Obj.
Erroe
Time
CPLEX
0.00
513.82
0.00
513.82
0.00
16s
0.00
510,08
510.08
20s
Sceuario-M
1039.48
0.93
0.86
1039.48
0.93
0.8s
1039.48
0.93
0.8s
1271.23
1.21
0.6s
1271.23
1.21
0.6s
1271
1.21
0.6s
Solution-M
678.74
678.74
0.8g
729.81
729.81
0.51
729.81
0.2s
K-medoids
662.48
0.30
0.2s
585.66
0.14
0.38
546.51
0.06
0.58
684.71
0.34
0.3s
623.76
0.22
0.3s
583.25
0.14
0.5s
CVAE-SIP
622.98
0.23
548.45
0.07
0.68
527.59
0.03
0.9s
695.00
0.36
592.40
0.16
0.6s
555.35
0.09
0.9s
CVAE-SIPA 562.87
0.11
0.5s
551.94
0.07
0.68
531.94
0.04
0.8s
622.91
0.22
0.5s
592.91
0.16
0.6s
$40.54
0.06
0.96
NDP (14; 200) DO
NDP (14;
K=3
K=55
K=10
K=3
K=5
K=10
Method
Obj
Emor
Time
Obj.
Firor
Time
Obj.
Error
Time
Obj
Emar
Time
Obj.
Froo
Time
Obj.
Error
Time
CPLEX
563.16
0.00
17s
563.16
0.00
17s
563.16
0.00
17s
617.21
0.00
17s
617.21
0.00
176
617.21
0.00
17s
Scenario-M M 1061.20
0.87
1061.20
0.87
1061.20
0.7%
1434,12
1434.12
1.37
1434.12
0.9g
Solution-M
754.11
0.38
0.6s
754.11
0.38
0.68
754.11
0.38
0.68
1282.59
1.12
0.6s
1282.59
1.12
0.6s
1282.5
39
1.12
0.6s
K-medoids
1086.43
0.93
744.53
0.32
0.48
635.58
0.5s
1091.11
0.79
0.3s
816.62
0.33
0.3g
692.81
0.12
0.6s
CVAE-SIP
1070.44
0.89
0.6s
698.18
0.24
0.68
632.03
0.12
0.9s
1180.53
0.90
0.6s
809.02
0.31
0.6s
675.19
0.09
0.9s
CVAE-SIPA
678.80
0.20
663.97
0.18
0.68
578.57
0.8s
758.14
0.23
737.81
0.19
643.50
0.04
0.8s
G GENERALIZATION ACROSS DISTRIBUTIONS AND DEPENDENCIES
We test the generalization performance of our method on NDP with scenarios sampling from the Normal distribution and Binomial distribution. For the former, we set the expectation and standard deviation to 10 and 2, respectively. For the latter, we set the number of runs and the probability to 20 and 0.5. The results are summarized in the upper half of Table 5 We observe that our methods con- sistently outperform other learning based approaches with scenarios from both distributions. When K=10, both CVAE-SIP and CVAE-SIPA achieve near-optimal solutions with slight approximation errors. On the other hand, it can be found that the results delivered by CVAE-SIPA are generally superior or comparable to those by CVAE-SIP, suggesting better cross-distribution generalization.
In our training, we do not assume explicit dependencies between the context and scenarios, following the settings in (Keutchayan et al. 2020 Nair et al. 20188] Abbasi et al. 2020). However, would like to show that the trained networks can well generalize to the dependent settings. In specific, we construct in NDP two dependencies between the demand scenarios and costs in contexts as follows:
16

---

Published as a conference paper at ICLR 2022
NOP 200g, Prediction
NOP144: 200y Freditiin
NOF11R 500g Fredictin
OB
10
-10
1.
-20
-14
-0.
NOP114; 2002 Target
NDP14K 200 Targe!
NOPLT4 9031 Target
10
-10
-12
Figure 3: Objective prediction against latent representations (NDP)
FLPIR 2007 Predidion
FLP/100 2009 Prediriinn
FuPgo 800) Prwdictoo
Oli
Ok
025
690
690
ETD
-1.
-10
10.
00
D0
110
13
-1.00
10/0
1000
-0.23
0.00
0.0
000
075
PUP.DO 209p:Trrge Target
FLP(120 200 Target
FLPIO BO0% Target
CN
CN
023
620
C20
US
105
05
10
15
1.00
10755
10.00
2.25
6.00
225
0.50
075
Figure 4: Objective prediction against latent representations (FLP)
1) DO: for each instance, the lower bound of Uniform demands is determined by the smaller value of the average opening and shipping cost in the context; 2) D1: the lower and upper bounds of Uniform demands are determined by the smaller and larger value of the average opening and shipping cost, respectively. We generate 50 instances for each dependency. From the lower half of Table [ we observe that our methods outperform learning based baselines except the cases with K=3, where CVAE-SIP loses its ad adnatage over a few baselines. Generally, it indicates that our methods possess fairly good generalization abilities to the setting where scenarios depend on the contexts.
H RESULTS ON OBJECTIVE PREDICTION
We first evaluate our trained model for the prediction task in three FLP instances, which are ran- domly generated from FLP (30; 200), FLP (120; 200) and FLP (30; 800), respectively. For each instance, we draw a scatter plot of the 2-dimensional latent representations for scenarios and repre- sent the normalized objective values using different colors. The results are shown in the upper half
17

---

Published as a conference paper at ICLR 2022
Table 6: Comparison with OR methods
NDP (14; 200)
FLP (30, 200)
K=5
K=10
K=20
K=5
K=10
K=20
Method
Obj.
Error
Time
Obj.
Error
Time Obj.
Error
Time
Obj
Emror
Time
Obj.
Error
Time
Obj.
Error
Time
CPLEEX
635.75
0.00
635.75
0.00
18s 635.75
18s 236.71
18c 236.71
0.00
18s 236.71
0.00
CSSC
695.08
0.10
17s 689.43
0.09
17s 669.59 0.05
30s 338.84
0.39
12s 299.42 0.23
12s 264.98 0.16
14s
Scen-red
951.54
0.50
739.41
0.18
0.5x 650.80
1s
640.07
0.3x 323.34
0.29
0.3s 246.57 0.08
CVAE-SIP
930.73
0.48
0.7s
734,24
0.15
0.9s 637.99 0,02
Is 929.61
2.87
0.7s
482.70
0.99
0.7s
282.49 0.23
1s
CVAE-SIPA
769.70
0.24
687.68
0.08
0.8s 642. 0.03
709.08
0.6s
381.41
0.58
0.7s 264.01
0.15
NDP (44; 200)
FLP (120: 200)
K=5
K=10
K=20
K=5
K=10
K=20
Method
Obj.
Emor
Time
Obj-
Error Time Obj.
Error
Time
Obj.
Eroo
Time
Obj-
Error
Time
Obj.
Error
Time
CPLEX
580.67
0.00
23m 580.67
0.00
23m 580.67 0.00
23m
484.60
0.00
1b
484.60
0.00
1h
484.60
0.00
lh
CSSC
618.10
0.07
617.94
0.07
2m
612.77 0.06
4m
1101.83
1.28
34s
844.24
0.76
42s
715.46
0.59
Scea-red
894.90
0.57
3s 667.90
0.15
6s 616.23
0.07
15s
1056.69
1.19
66
793.45
0.68
15s
607.69
0.26
60s
CVAE-SIP
0.84
615.99 0.06
588.18
16s
1585.53
12s
985.45
627.30
0.28
CVAE-SIPA
682.35
0.17
5s 627.62
0.08
8s 581.07
0.00
178
2051.45
3.13
16s
910.50
0.84
33s
594.33
0.22 698
of Figure 4 and the corresponding ground truth (i.e. optimal solution values attained by CPLEX) are displayed in the lower half. It is clear that the prediction is fairly accurate with almost the same patterns as the target values in the ground truth, even for the larger problem size or scenario cardi- nality. It indicates that our design for supervisd learning is effective and the trained model exhibits a desirable generalization ability.
We further evaluate the objective prediction on NDP. Specifically, the trained model is used to predict objective values for the scenarios from three instances, which are randomly generated from NDP (14; 200), NDP (44; 200) and NDP (14; 800), respectively. From the results in Figure we observe that our method can also predict the objective values accurately for NDP. Especially, the pattern of predicted values for NDP (14; 800) is almost indistinguishable from the one by ground truth. reveals that our design for the semi-supervised learning is effective across distinct SIPs.
I COMPARISON WITH OR METHODS
In this section, we compare our methods with two mature methods from operations research (OR), i.c., 1) Scen-red (Heitsch & Römisch 2003). which seeks a subset of scenarios that is closest to original scenarios in terms of Portet-Mourier probability metric, and 2) CSSC (Keutchayan et al,, 2020), which solves a MILP to derive representative scenarios, each of which estimates the average objective of some other scenarios. They are on behalf of the distribution-orientee oriented paradigm, respectively. The tested instances are the same as the ones in Section 5.2 and [5.3 From the results in Table 6 we observe that our methods are comparable to or better than the baselines and especially on NDP. While CVAE-SIP and CVAE-SIPA are inferior to CSSC NDP with K=5, they attain the best approximate solutions when K=10 and 20. Notably, the errors of our methods are close 0 on both normal and large instances when K=20. For FLP, while our methods are inferior to CSSC and Scen-red on FL.P when K=5 and 10, CVAE-SIPA surpasses CSSC on FLP (30; 200) and gains the smallest objective value and error on FLP (120; 200), when K=20. Since our runtime is shorter than CSSC and similar to Scen-red, the results again verify that our methods are effective to reduce scenarios for good approximations.
and problem-
J ABLATION STUDY
We further conduct an ablation study on NDP to verify the effectiveness of the learned scenario representations, and meanwhile investigate the mixed use of these representations with the original scenarios. In specific, we enrich the original scenario set for clustering in the following ways: 1) CVAEESIPA+Ori: we concatenate the predicted objective values with their original scenarios (rather than the learned representations in CVAE-SIPA); 2) CVAE-SIP+Ori: we concatenate the learned representations with their original scenarios (rather than merely use the learned representations in CVAE-SIP). These two kinds of mixed representations are used for clustering to find representative scenarios, where we set K=5, 10, 20. The tested instances are the same as the ones in Section 5.2 and 5.3
As shown in Table 6 both CVAE-SIP and CVAE-SIPA are generally superior their
18

---

Published as a conference paper at ICLR 2022
Table 7: Ablation study
NDP (14;200)
NDP (44; 200)
K=5
K=10
K=20
K=5
K=10
K=20
Method
Obi.
Emor
Time
Obj
Eror
Time
Obj.
Eror
Time
Obj.
Error
Time
Obj.
Eroor
Time
Obj.
Error
Time
CPLEX
635.75
635.75
0.00
580.67
0.00
23m
580.67
23m
K-medoids
976.47
0.54
0.3s 761.18
0.19 0.6s 677.02
0.08
803.99
0.38
3s 652.78
0,12
7s
595.15
0.04
14s
CVAE-SIPA+Ori
741.81
0.09
CVAE-SIPA
769.70
0.24
0.6s
687.68
0.08
0.85 642.12 0.03
682.35
0.17
5s 627.62
0.08
8s 581.07
0.00
17s
CVAE-SIPHOri
1208.19
0.06
1056.61
CVAE-SIP
930.73
0.48
0.7s 734.24 0.15 0.9s 637.99 0.02
1079.80
0.84
5s
615.99
0.06
8s 588.18
0.02
16s
Bold means the method outperforms counterpart.
counterparts. The advantage of CVAE-SIPA over CVAE-SIPA+On. indicates that with the same predicted objective values, our learned representations are effective to attain better representatives than the original scenarios. Moreover, CVAE-SIP is superior CVAE-SIP+Ori. probably because the learned representations are overwhelmed by the original scenarios to some extent. It is also interesting to identify an advantage that CVAE-SIP K-medoids CVAE-SIP+Ori, which means the pure use of learned representations or original scenarios is better than the mixed use of both.
19


Reviews:
[{"review_id": "gbENUrmDJCb", "reviewer": "Reviewer_Qekv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "AFTER REBUTTAL:\n\nI thank the authors for providing a detailed rebuttal with several additional experiments. \n\nIn 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.\n\n\n----------------\n\nThe 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. \n\nI have two major concerns:\n\n1. 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? \n\n\n2. 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.\n\n\n[1] Kipf & Welling, Variational Graph Auto-Encoders (2016)\n\n[2] Chai, Liu, Duffy, & Kim, Learning to Synthesize Cortical Morphological Changes using Graph Conditional Variational Autoencoder (2021)\n\n[3] Rujeerapaiboon, Schindler, Kuh, & Wiesemann, Scenario Reduction Revisted: Fundamental limits and guarantees (2018) \n\n\n", "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.\n", "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.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "aU8A0Vaj1D", "reviewer": "Reviewer_2AQy", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "$\\textbf{Strengths}$ \n-\tThis paper tackles a challenging problem. It is significant if one can reduce the number of scenarios required for obtaining a high-quality approximation \n-\tUsing CVAE for generating effective scenarios is an interesting idea. \n-\tThe paper provides detailed experimental settings, which are very helpful.\n\n$\\textbf{Weaknesses}$ \n\nI 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.\n\nMain concerns:\n-\tIn 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. \n-\tWhile 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). \n\nMinor concerns:\n-\tGiven 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. \n-\tI 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). \n-\tThe 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?\n-\tIt would be better to experimentally justify the choice of the dimension of c and z.\n-\tIt 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.\n-\tThe 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. \n-\tThe 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. \n", "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. ", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Wpy_apo_eGf", "reviewer": "Reviewer_tf4e", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Pros:\n* 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.\n* The paper shows improved performance over 2 recent baselines. While the performance falls short of the CPLEX solver, the proposed approach is generally faster.\n* 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.\n\nLimitations:\n* 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).\n* 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.\n\nClarity:\n* 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\").\n\n**Updated after rebuttal**\n\nI think the authors have addressed the concerns I have raised and I have increased my score.", "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.\n\nThe 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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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)