Neur2RO: Neural Two-Stage Robust Optimization
Authors: Justin Dumouchelle
Esther Julien
Jannis Kurtz
Elias Boutros Khalil
Venue: ICLR 2024 poster (2024)
Keywords: robust optimization
deep learning
discrete optimization
Primary area: optimization
TL;DR: This work proposes a learning-based algorithm to compute high-quality solutions for two-stage robust optimization problems via embedding trained neural networks to create a tractable surrogate optimization model.

Abstract: Robust optimization provides a mathematical framework for modeling and solving decision-making problems under worst-case uncertainty.  This work addresses two-stage robust optimization (2RO) problems (also called *adjustable robust optimization*), wherein first-stage and second-stage decisions are made before and after uncertainty is realized, respectively.  This results in a nested min-max-min optimization problem which is extremely challenging computationally, especially when the decisions are discrete.  We propose Neur2RO, an efficient machine learning-driven instantiation of column-and-constraint generation (CCG), a classical iterative algorithm for 2RO.  Specifically, we learn to estimate the value function of the second-stage problem via a novel neural network architecture that is easy to optimize over by design. Embedding our neural network into CCG yields high-quality solutions quickly as evidenced by experiments on two 2RO benchmarks, knapsack and capital budgeting. For knapsack, Neur2RO finds solutions that are within roughly $2$% of the best-known values in a few seconds compared to the three hours of the state-of-the-art exact branch-and-price algorithm; for larger and more complex instances, Neur2RO finds even better solutions. For capital budgeting, Neur2RO outperforms three variants of the $k$-adaptability algorithm, particularly on the largest instances, with a $10$ to $100$-fold reduction in solution time. Our code and data are available at https://github.com/khalil-research/Neur2RO.

Published as a conference paper at ICLR 2024
NEUR2RO:
NEURAL TWO-STAGE ROBUST OPTIMIZATION
Justin Dumouchelle'
Esther Julien TU Delft
Jannis Kurtz University of Amsterdam
Elias B. Khalil
University of Toronto
University of Toronto
ABSTRACT
Robust optimization provides a mathematical framework for modeling and solv- ing decision-makee making problems under worst-case uncertainty. This work addresses two-stage robust optimization (2RO) problems (also called adjustable robust op- timization). wherein first-stage and second-stage decisions are made before and after uncertainty is realized, respectively. This results in nested min-max- min optimization problem which is extremely challenging computationally, es- pecially when the decisions discrete. We propose Neur2RO, an efficient ma- chine learning-driven instantiation of column-and-constrainn generation (CCG), classical iterative algorithm for 2RO. Specifically, value function of the second-stage problem via a novel neural network archi- tecture that is easy optimize over by design. Embedding our neural net- work into CCG yields high-quality solutions quickly as evidenced by experi- ments two 2RO benchmarks, knapsack and capital budgeting. For knap- sack, Neur finds solutions that are within roughly 2% of the best-known values in few seconds compared to the three hours of the state-of-the-arr exact wranch-and-price algorithm; for larger and more complex instances, Neur2R0 finds even better solutions. For capital budgeting, Neur2RO outperforms three variants of the k-adaptability algorithm, particularly on the largest instances, with a 10 to 100-fold reduction in solution time. Our code and data are available at https::/ /ttp://iitthii com haomm/haailn wew.lll-eeeercceeeeeeeee Neechre
learn to estimate the
INTRODUCTION
wide range real-world optimization problems in logistics, finance, and healthcare, among others, can be modeled by discrete optimization models (Petropoulos et al. (023). While such mixed-integer (linear) problems (MILP) can still be challenging to solve, the problem size that can be tackled with modern solvers has increased significantly thanks to algorithmic developments [Wolsey] 2020 Achherberg & Wunderling) 2013). In recent years, the incorporation of Machine Learning (ML) models into established algorithmic frameworks has received increasing attention (Zhngg et al. 2023 Bengio et al. (0211)
While most of ML for discrete optimization has focused on deterministic problems, in many cases, decision-makers face uncertainty in the problem parameters, e.g., due to forecasting or measure- ment eтrоrs in quantities of interest such as customer demand in inventory management. Besides the stochastic optimization approach, for which learning-bass based heuristics have been proposed re- cently (Dumouchelle et al. 2022), another popular approach to incorporate uncertainty into opti- mization models is robust optimization, where the goal is to find solutions which are optimal con- sidering the worst realization of the uncertain parameters in a pre-defined uncertainty set (Ben-Tal) al. 2009). This more conservative approach has been extended to two-stage robust problems (2RO) where some of the decisions can be made on the fly after the uncertain parameters are real- ized (Ben-Tal et al. 2004); see Yanıkoğlu et al. (2019) for survey.
Example (Capital Budgeting). As a classical example a two-stage robust problem, consider the capital budgeting problem as defined in /Subramanyam et al. (2020) where company decides to invest in a subset of n projects. Each project has an uncertain cost (g()) and an uncertain profit
"Coreesooniigg author: fusii..uumoccchllll@ill......m

---

Published as a conference paper at ICLR 2024
(E) that both depend the nominal cost and profit, respectively, and some risk factor that dictates the difference from the nominal values to the actual ones. This risk factor, which we call an uncertain scenario, is contained in given uncertainty set E. The company can invest in project either before or after observing the risk factor &. up to a budget B. In the latter case, the company generates only fraction 1/ of the profit, which reflects a penalty of postponement. The objective of the capital budgeting problem is to maximize the total revenue subject to the budget constraint. This problem can be formulated as:
max min max xEX EEE yey
r(f) + ny)
(Ia)
s.t.
+ c( (x yx B
(1b) (1c)
Here, X' ='= {0, and zj and Y/ are the binary variables that indicate whether the company invests in the i-th project in the first- or second-stage, respectively. Constraint [Tb] ensures that the company can invest in each project only once and constraint Ic ensures that the total cost does not exceed the budget.
2RO with integer decisions is much harder to solve than deterministic MILPs, especially when the uncertain parameters appear in the constraints and the second-stage decisions are discrete. Even evaluating the objective value of a solution in this case is algorithmically challenging (Zhao & Zeng 2012). In Subramanyam et al. (2020), none of the generated capital budgeting instances could be solved even approximately in a two-hour time limit for 25, terminating with optimality gap of around 6%. In contrast to deterministic optimization problems, there is only limited literature on using ML methods to improve robust optimization (Julien et al.! 2022 Goerigk & Kurtz 2022).
Contributions. We propose Neural Two-stage Robust Optimization (Neur2RO) an ML framework that can quickly compute high-quality solutions for 2RO. Our contributions
follows:
ML in a novel optimization setting: 2RO (also known as adjustable RO) has been receiv- ing increased interest from the operations research community (Yamkoğlu et al. 2019) and our work is one of the first to leverage MI in this setting.
ML at the service of classical optimization algorithm: to deal with the highly con- strained nature of real-world optimization problems and rather than attempting to predict solutions directly, we "neuralize" well-established 2RO algorithm, a strategy that com- bines the best of both worlds: correctness of an established algorithm with the predictive capabilities of accurate neural network.
A compact, generalizable neural architecture that is reprereepeeeeetbble and estimates the thorny component of a 2RO problem. namely the value of the second-stage problem. The network is invariant to problem size and parameters, allowing, for example, the use of the same architecture for capital budgeting instances with a different number of projects and budget parameters.
Competitive experimental results on capital budgeting and two-stage robust knapsack problem, both benchmarks in the 2RO literature. Neur2RO finds solutions that of sim- ilar quality to or better than the state of the art. Large instances benefit the most from our method, with 100x reduction and 10 100x reductions in running time for knapsack and capital budgeting, respectively.
BACKGROUND
2.1 TWO-STAGE ROBUST OPTIMIZATION
2RO problems involve two types of decisions. The first set of decisions, x, are referred to as here- and-now decisions and are made before the uncertainty is realized. The second set of decisions,
y, are referred to as the wait-and-see decisions and can be made on the fly after the uncertainty realized. The uncertain parameters & are assumed to be contained in a convex and bounded uncertainty set E c R7. The 2RO problem aims at finding a first-stage solution x which minimizes the worst-case objective value over all scenarios & E, where for each scenario the best possible
2

---

Published as a conference paper at ICLR 2024
second-stage decision y() is implemented. Mathematically, 2RO problem is given by
min max min xEX EE= yEy c(E) d()))+
(2a)
s.t. T(E)+ [E)x+W(EE) (() h(E).
(2b)
where C R" and y C RT are feasible sets for the first and second stage decisions, respectively. In this work, we consider the challenging case of integer sets X' and y. All parameters of the
problem, namely c(E) E R", d(E) E R.", (E))) E Rrxm T(E) E R'**, and h(E) E R' depend on the scenario We make the following assumption which satisfied for the capital budgeting problem (and implicitly knapsack, which does not involve constraint uncertainty).
Assumption. For every X, we have method which calculates scenario E for which the second-stage constraints T y & h(g) over y E y are infeasible or verifies that no such scenario exists.
Both single- and multi-stage robust mixed integer problems are NP-hard even for deterministic prob- lems which can be solved polynomial time Buchheim & Kurtz (2018). Compared to single-stage problems, which are often computationally tractable as they can be solved using reformulations [en- Tal al. (2009) or constraint generation Mutapeic & Boyd (2009), two-stage problems are much harder to solve. When dealing with integer first-stage and continuous recourse, CCG is one of the key approaches ZZng Zhao (2013); Taang et al. (2023). However, many problems, such as the ones we study here, deal with (mixed- Jinteger second-stage decisions. While an extension of CCG has been proposed that able to handle mixed-integer recourse Zhao & Zeng (2012), this method not well-established and often intractable and the results do not apply for pure integer second-stage problems.
In the case that the uncertainty only appears in the objective function, the 2RO be solved by oracle-based sranch-and-bow methods (Kämmerling & Kurtz, 2020). branch-ande -ahh-rre-- (Arslan & Detienne, 2022), iterative cut generation using Fenchel cuts (Detienne al. 2024). For special problem structures and binary uncertainty sets, a Lagrangian relaxation can be used to transform 2RO problems with constraint uncertainty into 2RO with objective uncertainty which then be solved by the aforementioned methods (Subramanyam) 2022 Lefebvre et al. (2023).
2.2 COLUMN-AND-CONEN
GENERATION
The main idea of CCG to iterate between main problem (MP) and an adversarial problem (AP)- The MP is relaxation of the original problem that only considers finite subset of the uncertainty set E' C E. The latter problem can be modeled as a MILP by introducing copies of the second- stage decision variables y for each of the scenarios in E'. After calculating an optimal solution of the MP. the AP finds new scenarios in the uncertainty set that cut off the current solution in the MP. When such scenario can be found, the optimality of the current MP solution is guaranteed. For mathematical formulations of the two problems and a more detailed description of the CCG procedure, see Figure D and Appendix B.I
CCG often fails to calculate an optimal solution in reasonable time since both the MP and the AP very hard solve. In each iteration, the size of the MP increases leading to it being difficult to solve to optimality even with commercial MILP solvers such as Gurobi (Gurobi Optimization, LLC, 2.23). Furthermore, solving the AP is extremely challenging for integer second-stage variables. In Zhao & ZZeng (2012). the authors present column-and cottm---nd-ooosrraiiiin algorithm which solves the AP if the second stage a mixed integer problem; this leads CCG for the AP inside the main CCG, most intractable combination. Additionally, the method Zhao & Zeng (2012) is not applicable to purely integer second-stage decisions such as the problems we consider here.
METHODOLOGGY
At a high level, our approach aims to train a neural network that predicts the optimal second-stage objective value function and then integrates this model within CCG framework to obtain first-stage decisions. We rely on a training dataset of historical instances that can be used or generated, as is typically assumed in -ioiiriootinnization work.
3

---

Published as a conference paper at ICLR 2024
min 84.
OCG
< d(E) s VE
T(px Wiggr & h(g) EE
maxmin
< d(E)'
CCG
st.
Wigly & b/()
T(Exx
main
NeuzRRO
MAIN PROBLEM (E)
AIDVERSARIAL PRORI FM (x*)
NeuCRO
NNu(x
s.1. <(C.) x d(
T) W(E.) h((.)
Add 4 to
4. ang g (x.
No. Optinal
Optinaal
Temminate
Figure 1: Columm-and-constraantt generation: in each iteration, a main problem (box (a)) is solved to find a good first-stage solution x* for the set of scenarios that have been identified thus far (initially, none). Then, an adversarial problem (box (c)) is solved to obtain new scenario for which the solution x* is not feasible anymore in MP. If no such scenario exists, then x* is optimal and CCG terminates. Otherwise, the adversarial scenario is added to the set of worst-case scenarios and we iterate MP. For each of the MP and AP, show two versions: classical (CCG, boxes (a) and (c)) and
2Neur dashed boxes (b) and (d)).
3.1 LEARNING MODEL
As mentioned before, CCG is computationally very expensive. Both the MP and AP contribute to its intractability (see Figure boxes (a) and (c) for descriptions). In the MP, for each added scenario, new second-stage decision y is introduced. When a large number of scenarios are required to obtain robust solution, the number of variables grows rapidly. Moreover, the AP is especially hard when the second-stage decisions are integer, which is the case we consider. In our learning -uggmenedd approach, we replace the intractable elements of the CCG with MILP representations of trained NN which is computationally much easier to handle (Figure 1
We train a neural network that can accurately predict the optimal value of the second-stage problem for given input of first-stage decision, an uncertainty realization, and the problem's 's specification, P. The problem specification refers to the coefficients and size of the optimization problem, e.g., the nominal values of the profit and costs in the capital budgeting problem. More formally we train a neural network (.)..), to approximate the optimal value of the integer problem
N (x, E, ss yE>
y WP) S hp (E)))))
where θ are the weights of the neural network. For ease of notation, we hereafter omit P in the formulation. For more details on the architecture of N (Ne(.), see Section 3.3 Alternatively, as cp (P(E)Tx is scalar product of the input vectors, instead could only predict the second-stage ob- jective, i.e., ( subject to the same constraints. However, as demonstrated in Appendix H.3 predicting the sum of first- and second-stage objectives achieves higher-quality solutions.
3.2 ML-BASED BOLUMN-AND-CONSTTRR
GENERATION
Having defined the learning task, we now describe the ML-based approximate CCG algorithm. For an overview of this method, see Figure
Main Problem. Given finite subset of scenarios E' E. we reformulate the MP using an arg max operator which selects a scenario that achieves the worst objective function value when replacing the second-stage objective value by the neural network formulation.
min XEE
c(E,) Tx + d
(4a)
s.t. W(g.)y + T(E.)x & h(ga). Ea E arg max Ne }
(4b)
(4c)
Modeling the arg max can be done by adding additional linear constraints and binary variables, which we explicitly show in Appendix The MP results in MILP formulation.
4

---

Published as a conference paper at ICLR 2024
This formulation is indeed not the only option; for example, could instead consider another for- mulation, called max, which provides a more intuitive formulation and does not require modeling second-stage variables; details provided in Appendix H.T
However, equation 4 has one key property that motivates its efficacy. From the machine learning perspective, rather than requiring a neural network be accurate estimator of the objective for each scenario, we only require that the neural network be able to identify the maximal scenario. Prediction inaccuracy is then compensated for in equation by exactly modeling the second-stage cost. As result, when solving the MP, the true optimal first-stage decision for the selected scenario will be the minimizer, rather than poten- tially suboptimal first-stage decision based on any inaceuracy of the learning model. Appendix [H.]] presents ablation comparing both the solution quality of the arg max and max formulations on the knapsack problem, and establishes that the arg max formulation indeed computes higher quality solutions across every instance.
Ad Adversarial Problem. y by its prediction N Ne E), where x* is given (see Figure [ box (d)). When we deal with constraint uncertainty, we first check there exists scenario 5 E E. such that no feasible y E y exists for the constraints
In the AP of Neur we replace the inner optimization problem over
(E) + T()xx* < h()),
which we can do by the assumption from Section 2.1 If such scenario exists, we add it to E' and continue with solving the MP again. Note that in this case
not feasible for MP in the calculate optimal solution &* of the AP in box (d) of Figure [ which can be done by using the MILP representation for NN. Note that an ellipsoid, then this problem results in mixed-integer linear or quadratic
next iteration. If no such scenario could be found,
E is polyhedron problem, respectively, which can be solved by state-of of-te-of-hhh-rr the-art solvers such as Gurobi. We compare the optimal value of the latter problem with the objective values of all scenarios that were considered in the MP before. If the following holds
max NN .E) 2 max NNo"x", + EEE'
(5)
EEE
for a pre-defined accuracy parameter & > O, then we add 5" to E' and continue with the MP. Otherwise, stop the algorithm. Finally, note that we can calculate both types of scenarios in each iteration and add them both to E' before we iterate to the MP. As the adversarial problem requires finding the worst-case uncertainty over neural network's 's input, heuristic approaches may significantly improve solving time with minimal degradation in solution quality. Appendix H.2 presents an ablation demonstrating significantly lower solution time minimal cost of solution quality for sampling- and relaxation-basee heuristics.
Convergence. Since our algorithm does not apply the standard CCG steps, the convergence guar- antee from the classical algorithm does not hold. However, we prove in Appendix FF that it holds if only finitely many first-stage solutions exist, which the case if all first-stage variables are integer and X' is bounded; this indeed holds for the knapsack and capital budgeting problems.
Theorem 1. If X is finite, the ML-based CCG terminates after a finite number of iterations.
3.3 ARCHITECTURE
For the ML-based CCG, one requirement is the optimization, in each iteration, over several trained neural networks in the MP (one for each scenario in equation and single trained neural network in the AP. Generally, increasing the size of the networks will lead to more challenging and potentially intractable optimization problems. For that reason, developing an architecture that can be efficiently optimized over is crucial aspect of an efficient ML-based CCG algorithm.
To achieve efficient optimization, we embed the first-stage decisions, x, and a scenario, E. into low-dimensional embeddings using networks Øx and &. respectively. These embeddings are con- catenated and passed through a final small neural network (the Value Nenwork) that predicts the objective of the optimal second-stage response; see Figure 2 a pictorial representation.
Main Problem Optimization. When representing the trained models in the MILP, we only have to represent the embedding network Φx and the small value network b which can be done by classical MILP representations of ReLU NNs (Fischetti & Jol 2018). Since the scenario parameters not variables here, the scenario embeddings (E((") can be precomputed via forward pass
5

---

Published as a conference paper at ICLR 2024
First-stage Embedding
Network
x (xx)
x" E X
Value cb Network
$ (concat (xxe)), & $c(5*))
Scenario
&
estimate for
Embedding
Network
c(t*) Tx" min yey
d(E*)Ty
$E(E*)
W(E")y h(ee) T((")x**
Figure 2: Neural network architecture for ML-based CCG. The current first-stage solution, x", is embedded once using the network (+))). scenario & embedded using network (.(.). To estimate the value of the second-stage optimization problem corresponding to particular pair (x*.$* the two embedding vectors are concatenated into one (dashed arrows) and then passed into the final Value Network.
for each scenario, i.e., no MILP representation is needed for Øg. If / is a small neural network, then representing large number of copies of the network (one per scenario) remains amenable to efficient optimization.
Ad veresarial Problem Optimization. For the AP, only require representing &g and & as the embedding of x can be precomputed with a forward pass.
Generalizing Across Instances. For simplicity of notation and presentation, the previous sections have omitted the generalization across instances, which is a key aspect of the generality our methodology. To generalize across instances, invariance the number, ordering, constraint coeffi cients, and objective coefficients of decision variables is required. To handle this, Neur2RO lever- ages set-based neural networks (Zaheer et al., 2017) for 4x and dgg. Specifically, embeddings are computed for each single first-stage and scenario variable (I; and {,) using their values, constraints, and objective coefficients, via network with shared parameters. These embeddings are then ag- gregated and passed through additional feed-forward neural network to derive the first-stage and scenario embeddings. For detailed diagram of this architecture, see Appendix
EXPERIMENTAL SETUP
Computational Setup. All experiments were run on a computing cluster with an Intel Xeon CPU ES-2683 and Nvidia Tesla P100 GPU with 64GB of RAM (for training). Pytorch 1.12. (aazkee et al. 2019) was used for all learning models. Gurobi 10.0.2 (Gurobi Optimization, LLC, 2023 was used as the MILP solver and gurobi-machineleaming 1.3.0 was used to embed the neural networks into MILPs. For evaluation, all solving was limited to 3 hours. For Neur2RO, terminate solve of the MP or AP carly if no improvement solution is observed in 180 seconds. Our code and data /ttt::///ittutt cheeee/haalrrrrerrhchhhheccc NNuur2R
We benchmark Neur on two 2RO problems from the literature, namely a two-stage knapsack problem and the capital budgeting problem. In both cases, instances as large or larger than considered in the literature. The two-stage knapsack problem is in the first stage classical knapsack problem. The second stage has decisions for responding an uncertain profit degradation. The capital budgeting problem is described in the introduction. For detailed description of these problems, see Appendix A Below briefly detail each problem.
2RO Problems.
Knapsack. For the knapsack problem, we use the same instances as Arslan & Detienne (2022), which have been inspired by Ben--aal al. (2009). They have categorized their instances into four groups: uncorrelated (UN), weakly correlated (WC), almost strongly correlated (ASC), and strongly correlated (SC), which affects the correlation of the nominal profits of items with their cost and, turn, the difficulty of the problem. More correlated instances are much harder solve. We consider instances of sizes E (20, 30, 40, 50, 60, 70, 80).

---

Published as a conference paper at ICLR 2024
Capital budgeting. These problem instances are generated similar to Subramanyam al. (2020). While uncertain parameters appear in the constraints (see equation|Lo Lcp. we can easily ver- ity the assumption given in Section 2.1 as follows: for every we check if maXęez c(E) S B, where the maximum can be easily calculated since it is a linear problem over E. If the lat- ter inequality is true, the second-stage problem is feasible since we choose y 0. On the other hand, if the inequality is violated, then no feasible second-stage solution exists since y 2 O, and hence the maximizing scenario will be added to MP. We consider instances of sizes n E (10, 20, 30, 40, 50}.
Baselines. For knapsack, we compare to the branch-and-price (BP) algorithm from Arslan & Deti- enne (2022), the sfate-of-the-an for 2RO problems with objective uncertainty. We use the instances and the objective values and solution times reported in their paper (link) For capital budgeting, we use the k-adaptabilityy approach of [Subramanyam et al. (2020) (more details in Appendix B.2) with k 2, 5, 10 as a baseline; CCG is not tractable for this problem due to its integer recourse.
After Neur2Ro finds the first-stage decision x', we obtain the corresponding objective value by Sol a fixed x. For knapsack, this can be efficiently solved by constraint generation of y. For capital budgeting on the other hand, due to constraint uncertainty, we cannot use the constraint generation approach. Instead we sample scenarios from E, and solve with fixed x and Ş. See Appendix Dareendxxfforr a more detailed explanation of these methods.
Evaluation.
As previously mentioned, we use k-adaptability as the baseline for the capital budgeting problem. This method solves only approximately with the approximation quality getting better with larger k at an increase in solution times. We take the first-stage solution found by k-adaptabilityy and compare it with the one of Neur using the scenario sampling approach just described.
For the evaluation of the objective values, two metrics are considered. We use relative error (RE), i.e., the gap to the best-known solution, compare solution quality. Specifically, if obj* is the value of the best solution found by Neur2RO or a baseline for a particular instance, then for algorithm A with objective objA, the RE is given by 100 lobj"- obii average solution time.
To compare efficiency, compare the
[ob3
Data Collection & Training. For data collection, we sample sets of instances, first-stage decisions, and scenarios to obtain features. The features are provided in Appendix Labels are then computed by solving the corresponding innermost optimization problem, i.e., a tractable deterministic MILP as both x and are fixed. Additionally, this process is highly parallelizable since each optimization problem is independent. For knapsack and capital budgeting, we randomly sample 500 instances, 10 first-stage decisions per instance, and 50 scenarios per first-stage decision, resulting in 250,000 data points. The dataset is split into 200,000 and 50,000 samples for training and validation, respectively.
We train one size-independent model for each problem for 500 epochs. The data collection times, training times, and total times (in seconds) are 2,162, 3,789, and 5,951 for knapsack and 3,212, 2,195, and 5,407 for capital budgeting. We note that both times are relatively insignificant given that we provide approximately twice the time (3 hours) to solve a single instance during evaluation. Furthermore, the model for Neur2RO generalizes across instance parameters and sizes. Appendix provides full detail on model hyperparameters and training.
5 EXPERIMENTAL RESULTS
For knapsack, we test our method and the baseline on 18 instances per correlation type and instance size (504 instances). For capital budgeting, we test on 50 instances per instance size (250 instances). We note that training and validation data are generated using the procedures specified in the corre- sponding papers, and different instances are used for testing. For optimization of N2Ur2RO, this section presents results for solving the MIP and MILP formulations for the MP and AP, with the arg max formulation outlined in Section for the MP. Tables [ the median RE and solving times. In addition, for more detailed distributional information, boxplots and more detailed metrics, are provided in Appendix G
Knapsack. Table I demonstrates clear improvement in scalability, with the solving time of Neur2RO ranging between and 77 seconds, while the solving time for BP seales directly with difficulty induced by the size and correlation type. For the more difficult instances, i.e. instances
7

---

Published as a conference paper at ICLR 2024
Conceltion Type
# items
Median RE
Times
Correlation Type
# itemss
Median RE
Tincs
Neuz2RO
Neur2RO
Neuz2RO
Neuz2R0
20
1.417
0.000
4
0
20
1.439
0.000
5
1.188
2708
1.614
0.000
Almost Strongly
0.497
0.000
10
4744
Uncorelated
50
1,814
0.000
9
12
50
0.019
0.000
7
8852
1.146
Concelated
0.000
14
10261
1,408
0.000
0.017
0.031
13
10800
80
0.968
0.,00
11
388
80
0.000
0.265
12
10800
1,582
0.000
20
1.604
0.000
30
2.236
0.000
11
454
30
0.610
0.000
7
2473
Weakdy
1.595
0.000
6179
Strongly Conclated
0,443
0.000
56665 11
Conclated
1.757
0.000
8465
0.073
0.000
8240
60
0,695
0.,00
77
9242
60
0.042
0.010
11
10800
0.165
0.020
16
0.000
0.341
10800
80
0.000
0.179
13
10800
Table 1: Median RE and solving times for knapsack instances. For each row, the median RE and average solving time are computed over 18 instances. All times in seconds. The smallest (best) values each row/metric are in bold.
items
Median
Times
Neu:2RO
à = 2
==
k 10
Neur2R0
k 2
A 5
k = 10
1.105
0.000
9561
20
0,000
0.196
0.112
0.064
324
8702
10800
10800
0.109
0.020
0.073
0.032
602
10801
10800
10800
40
0,009
0.074
0.011
0.019
739
10806
10801
10801
50
0.001
0.033
0.039
0.020
1032
10807
10804
10801
Table 2: Combined results for capital budgeting instances. For each row, the median RE and average solving time are computed over 50 instances. All times in seconds. The smallest (best) values in each row/metric are in bold.
with large number of items and (almost) strong correlation, Neur2RO generally finds better quality solutions over 100 times faster than BP, which is very strong result considering BP is the state-of- the-art for problems with objective uncertainty. Figures 6 7 of Appendix further demonstrate that the distribution of RE achieved by Neur2RC, not just the median, is far more favorable than BP's on the most challenging instances. For easier instances, Neur2RO is less competitive terms of solution quality as BP converges to optimal solutions within the time limit. However, even for these instances, Neur2RO achieves median RE of 2.235% in the worst-case, often still 1-2 orders of magnitude faster than BP, with the exception of a few very easy instances.
Capital budgeting. Neur2RC achieves the lowest median RE for 20, 40, and 50-item instances, i.., the two largest and most challenging instance sets. The distribution of RE for 40 and 50-item instances provided in Figure g of Appendix G is indeed consistent with the median result, as illustrates that Neur2RC finds quality solutions on the majority of the instances. In terms of solving time, Neur2RG generally converges much faster than k-adaptability. resulting in a very favorable trade-off:: we can find better or equally good solutions 10 to 100 times faster. Note that the relative errors are quite small in an absolute sense. For example, for 30-item instances, Neur2RO has median RE of 001 compared the best baseline's 's 0.020; solutions that are within 0. 0099% of the best achievable may be acceptable in practice. Note that we have also measured the median RE for k-adaptability assuming a shorter time limit, namely the same amount of time as Neur2RO on each instance. Taking the incumbent solution found by k-adaptability at that time point typically yields worse solutions than those reported in Table 2 see Appendix H..4 for details. Compared to the knapsack, the solving time is generally much larger the instance size increases. We speculate that this may relate to the uncertainty the objective of the first-stage decision or the budget constraints that are not present in the knapsack problem.
In summary, for both benchmark problems, Neur2RO achieves high-quality solutions. For rela- tively easy or small instances. state-of-the-aal methods sometimes find slightly better solutions, often at a much higher computational cost. However, as the instances become more difficult, Neur2RO demonstrates clear improvement in overall solution quality and computing time.
8

---

Published as a conference paper at ICLR 2024
6 RELATED WORK
Robust optimization. Besides the exact solution methods mentioned in Section 2.1 several heuris-
tic methods have been developed to derive near-optimal solutions for mixed-integer 2RO problems.
Methods that solve 2RO heuristically are k-adaptability (Bertsimas & Caramanis, 2010 Hanasu-
santo et al. 2015) Subramanyam et al., 2020), decision rules (Bertsimas & Georghiou 2018 2015),
and iteratively splitting the uncertainty set (Postek & Hertog 2016). Machine learning techniques have been developed to speed up solution algorithms for the k-adaptability problem in Julien et al.]
(2022). In Goerigk & Kurtz (2022) a decision tree classifier is trained to predict good start scenar- ios for the CCG. While being heuristic solvers, all of the above methods are still computationally algorithm by |Subramanyam et al. (2020) is used as a baseline since it is one of the only methods which is able to calculate high quality solutions for reasonable problem sizes. For an elaborate overview of the latter algorithm, see Appendix B.2
highly demanding. In this paper, the k-adaptabilityy
Besides improving algorithmic performance, ML methods have been used to construct uncertainty sets based on historical data. In Goerigk & Kurtz (2023) one-class neural networks are used to construct highly complex and non-convex uncertainty sets. Results from statistical learning theory
are used derive guarantees for ML designed uncertainty sets in TTulabandhula & Rudin (2014).
Other approaches use principal component analysis and kernel smoothing (Ning & You 2018
support vector clustering (Shang et al., 2017 (Shan & You, 2019) [Shen et al. 2020), statistical
hypothesis testing (Bertsimas et al. 2018). or Dirichlet process mixture models (Ning & You 2017]]
Campbell& & How] 2015). In Wang et al. (202aa) uncertainty sets providing a certain probabilistic guarantee are derived by solving a Coaatcoostr bilevel problem by augmented Lagrangian method. While interesting and related, we here assume the uncertainty set is known.
MILP representations of neural networks. One key aspect of Neur2RO is representing neural networks as constraints and variables in MILPs, which was first explored in Cheng et al. (2017); Tjeng et al. (2017): |Fischetti & Jo (0188; : [Serra et al. (2018). These representations have motivated active research to improve the MILP solving efficiency of optimizing over-trained models Grimstad & Andersson 2019); Anderson al. (2020); Wang al. (2023b), well several software con- tributions Bergman et al. (2022): Ceccon et al. (2022), in addition to Gurobi, a commercial MILP solver, providing an open-source library. The use of embedding trained predictive models to de- rive approximate MILPs has been explored for non-linear constraints or intractable constraints (Say) al. 2017. Grimstad Andersson 2019; Murzakhanov et al. [2000] Katz al. 2020 Kody al.) 2022 stochastic programming (Dumouchelle et al.] 2022 Kronqvist et al. [202)), ) and bilevel op- timization (Dumouchelle et al. 2024). As Neur2RO is based on an approximation for intractable 2RO problems with embedded neural networks, the latter area of research is the most closely related. However, the min- can--max-maa optimization in 2RO renders previous learning-baad based MILP approxima- tions unsuitable.
7 CONCLUSION
With the uncertainty in real-world noisy data, the economy, the climate, and other avenues, there an increasing need for efficient robust decision-making. We have shown how Neur2RO uses MIL--reppeseentall feedforward neural networks to estimate the thorny component of a family of two-stage robust optimization instances, namely the value of the second-stage problem. The neural network architecture delicately combines din-dinenioonal embeddings of a first-stage decision and a scenario produce the second-stage value estimate. Using an off-the-shelf MILP solver, we then use the neural network in classical iterative algorithm for 2RO. Neur2RO to find competitive solutions compared to ofate-of-the-art methods on two challenging benchmark problems, knapsack and capital budgeting, at substantial reduction in solution time.
Our work paves the way for further integration of learning and optimization under uncertainty. The AP in the CCG algorithm is over the inputs of neural network, which could benefit from the many "adversarial attack" heuristics in the ML literature. Generalizations of Neur2RO that make predictions of the infeasibility of particular constraint could be explored. ReLU networks not the only class of models that is MILP repessebpes decision tree models could be used as alternatives and may be appropriate for other problem settings.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
Dumouchelle and Khalil acknowledge support from the Scale AI Research Chair Program and an NSERC Discovery Grant. Julien acknowledges funding from the Netherlands Organisation for Sci- entific Research (NWO).
REFERENCES
Tobias Achterberg and Roland Wunderling. Mixed integer programming: Analyzing 12 years of progress. In Facets of combinatorial optimization: Festschrift for martin grötschel, pp. 449-481.
Springer, 2013.
Ross Anderson, Joey Huchette, Will Ma, Christian Tjandraatmadja, and Juan Pablo Vielma. Strong Mexed-integer programming formulations for trained neural networks. Mathematical Program- ming, pp. 1-37, 2020.
Ayşe Arslan and Boris Detienne. Decomposition-bitn basso approaches for class of two-stage robust binary optimization problems. INFORMS journal computing, 34(2):857-871, 2022.
Ayşe N Arslan, Michael Poss, and Marco Silva. Min-sup-min robust combinatorial optimization with few recourse solutions. INFORMS Journal on Computing, 34(4):2212-2228, 2022.
Aharon Ben-Tal, Alexander Goryashko, Elana Guslitzer, and Arkadi Nemirovski. Adjustable robust solutions uncertain linear programs. Mathematical programming, 99(2):351-376, 2004.
Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust optimization, volume 28.
Princcton university press, 2009.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti-
mization: methodological tour d'horizon. European Journal of Operational Research, 290(2): 405-421, 2021.
David Bergman, Teng Huang, Philip Brooks, Andrea Lodi, and Arvind U Raghunathan. JANOS: an integrated predictive and prescriptive modeling framework. INFORMS Journal on Computing, 34(2):07-816, 2022.
Dimitris Bertsimas and Constantine Caramanis. Finite adaptability in multistage linear optimization. IEEE Transactions on Automatic Control, 55(12):2751-277) 2010.
Dimitris Bertsimas and Angelos Georghiou. Design of near optimal decision rules in multistage adaptive mixed-integer optimization. Operations Research, 63(3):610-62) 0200006672260 2015.
Dimitris Bertsimas and Angelos Georghiou. Binary decision rules for multistage adaptive mixed- integer optimization. Mathematical Programming, 167:395-433, 2018.
Dimitris Bertsimas, Vishal Gupta, and Nathan Kallus. Data-driven robust optimization. Mathemat- ical Programming, 167:235-299 2018.
Christoph Buchheim and Jannis Kurtz. Robust combinatorial optimizztinn under convex and discrete cost uncertainty. EURO Journal on Computational Optimization, 6(3):211-23) 2018.
Trevor Campbell and Jonathan P How. Bayesian nonparametric set construction for robust optimiza- tion. In 2015 American Control Conference (ACC), pp. 4216-4221. IEEE, 2015.
Francesco Ceccon, Jordan Jalving, Joshua Haddad, Alexander Thebelt, Calvin Tsay, Carl Laird, and Ruth Misener. OMLT: Optimization & machine learning toolkit. arXiv preprint arX1v:2202.024144, 2022.
Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. Maximum resilience of artificial neural networks. International Symposium on Automated Technology for Verification and Analysis, pp. 251-268. Springer, 2017.
10

---

Published as a conference paper at ICLR 2024
Boris Detienne, Henri Lefebvre, Enrico Malaguti, and Michele Monaci. Adjustable robust opti- mization with objective uncertainty. European Journal of Operational Research, 312(():373 2024.
Justin Dumouchelle, Rahul Patel, Elias B Khalil, and Merve Bodur. Neur2SP: Neural two-stage stochastic programming. Advances in Neural Information Processing Systems, 35, 2022.
Justin Dumouchelle, Esther Julien, Jannis Kurtz, and Elias B Khalil. Neur2BiL.O: Neural bilevel optimization. arXiv preprini arXiv:2402.02552, 2024.
Matteo Fischetti and Jason Jo. Deep neural networks and mixed integer linear optimization. Con- sfraints, 23(3):29--309, 2018.
Alireza Ghahtarani, Ahmed Saif, Alireza Ghasemi, and Erick Delage. A double-oracle, logic-based benders decomposition approach solve the k-adaptability problem. Computers & Operations Research. 155:106243, 2023.
Mare Goerigk and Jannis Kurtz. Data-driven prediction of relevant scenarios for robust optimization. arXiv e-prints, pp. arXiv-2203, 2022.
Mare Goerigk and Jannis Kurtz. Data-driven robust optimization using deep neural networks. Com- puters & Operations Research, 151:106087, 2023.
Bjarne Grimstad and Henrik Andersson. ReLU networks as surrogate models mixed-integer linear programs. Computers & Chemical Engineering, 131: 2019.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URL https: pectts://wwa
gurobi. com
Grani A Hanasusanto, Daniel Kuhn, and Wolfram Wiesemann. K-adaptabilityy in two-stage robust binary programming. Operations Research, (3(4):877881,200
Esther Julien, Krzysztof Postck, and & ilker Birbil. Machine learning for k-adaptability in two-stage robust optimization. arXiv preprint arXiv:2210.11152. 2022.
Nicolas Kämmerling and Jannis Kurtz. Oracle-based algorithms for binary two-stage robust opti- mization. Computational Optimization and Applications, 77:539-569, 2020.
Justin Katz, losif Pappas, Styliani Ayraamidou, and Efstratios N. Pistikopoulos. The integra- tion of explicit MPC and ReLUU based neural networks. IiAC--PaperSOnll.ne, 33(2):11300 11355, 2020. ISSN 2405-8963. doi htt.a//c...............aaaa////a 2 //www. wwwencediieect...c.mmm..... IFAC World Congress.
URL
Alyssa Kody, Samuel Chevalier, Spyros Charzivasileiadis, and Daniel Molzahn.
Modeling the AC power flow equations with optimally compact neural networks: Application to unit commitment. Electric Power Systems Research, 213:108282, 2022. ISSN 0378-7796.
URL https:/ //wp:///www.//////////..t//.. www.wceeeeedddeoooomo rect..
comm cttp://iiaanee/etcoeeee/////7770
Jan Kronqvist, Boda Li, Jan Rolfes, and Shudian Zhao. Alternating mixed-integer programming and neural network training for approximating stochastic two-stage problems. arXiv preprint arXiv:2305.06785. 2023.
Jannis Kurtz. Approximation algorithms for min-max-ni robust optimization and k-adaptability under objective uncertainty. arXiv preprint arXiv:2106.03107, 2023.
Henri Lefebvre, Enrico Malaguti, and Michele Monaci. Adjustable robust optimization with discrete uncertainty. INFORMS Journal Computing, 2023.
Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. Advances in neural information processing systems, 27, 2014.

---

Published as a conference paper at ICLR 2024
Ilgiz Murzakhanov, Andreas Venzke, George S Misyris, and Spyros Chatzivasilciadis. Neu- ral networks for encoding dynamic security-constrained optimal power flow. arXiv preprint arXiv:2003.07939, 2020.
Almir Mutapeie and Stephen Boyd. Cutting-set methods for robust convex optimization with pes- simizing oracles. Optimization Methods & Software, 24(3):381-406, 2009.
Chao Ning and Fengqi You. Data-driven adaptive nested robust optimization: general modeling framework and efficient computational algorithm for decision making under uncertainty. AIChE Journal, 63(9):3790-3817, 2017.
Chao Ning and Fengqi You. Data-driven decision making under uncertainty integrating robust opti- mization with principal component analysis and kernel smoothing methods. Computers & Chem- ical Engineering. 12:1900220, 2018.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buu E. Fox, and R. Garnett (eds.). Advances in Neural Information Processing Systems 32, pp. 8024-8035. Curran Associates, Inc., 2019. hatbhpeffommmeeeeelllleeen----rr
Fotios Petropoulos, Gilbert Laporte. Emel Aktas, Sibel A Alumur, Claudia Archetti, Hayriye Ayhan, Maria Battarra, Julia A Bennell, Jean-Marie Bourjolly, John Boylan, et al. Operational research: Methods and applications. arXiv preprint arXiv:2303. 140.1 2023.
Krzysztof Postek and Dick den Hertog. Multistage adjustable robust mixed-integed optimization via iterative splitting of the uncertainty set. INFORMS Journal on Computing, 28(3):553-574, 2016.
Buser Say, Ga Wu, Yu Qing Zhou, and Scott Sanner. Nonlinear hybrid planning with deep net learned transition models and mixed-integer linear programming. In ICCAI, pp. 750-756, 2017.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions deep neural networks. International Conference on Machine Learning, pp. 4558- 4566. PMLR. 2018.
Chao Shang and Fengqi You. A data-driven robust optimization approach to acenario-based stochas- tic model predictive control. Journal of Process Control, 75:24-39, 2019.
Chao Shang, Xiaolin Huang, and Fengqi You. Data-driven robust optimization based on kernel learning. Computers & Chemical Engineering, 106:464 479, 2017.
Feifei Shen, Liang Zhao, Wenli Du, Weimin Zhong, and Feng Qian. Large-scale industrial energy systems optimization under uncertainty: A data-driven robust optimization approach. Applied Energy, 259:114199, 2020.
Anirudh Subramanyam. A lagrangian dual method for two-stage robust optimization with binary uncertainties. Optimization and Engineering, 23(4):1831-187 2022.
Anirudh Subramanyam, Chrysanthos E Gounaris, and Wolfram Wiesemann. K-adaptabilityy in two- stage mixeddinteger robust optimization. Mathematical Programming Computation, 12:193-201 224224,, 2020.
Vincent Tjeng, Kai Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. arXiv preprint arXiv:1711.0736. 2017.
Man Yiu Tsang, Karmel Shchadeh, and Frank E Curtis. An inexact gellum--and-conseeee gener- ation method to solve two-stage robust optimization problems. Operations Research Letters, 51 (1):92-98, 2023.
Theja Tulabandhula and Cynthia Rudin. Robust optimization using machine learning for uncertainty sets. arXiv preprint arXiv: |407. 1097, 2014.
12

---

Published as a conference paper at ICLR 2024
Irina Wang, Cole Becker, Bart Van Parys, and Bartolomeo Stellato. Learning for robust optimization. arXiv preprint arXiv:2305. /9252, 2023a.
Keliang Wang, Leonardo Lozano, Carlos Cardonha, and David Bergman. Optimizing over an en-
semble of trained neural networks. INFORMS Journal on Computing, 35(3):552-67,,22 2023b.
Laurence Wolsey. Integer programming. John Wiley Sons, 2020.
Ihsan Yankoolu,, Bram Gorissen, and Dick den Hertog. A survey of adjustable robust optimiza- tion. European Journal of Operational Research, 277(3)799 813, 2019.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
Bo Zeng and Long Zhao. Solving two-stage robust optimization problems using a column-and- constraint generation method. Operations Research Letters, 41(5):457 461, 2013.
Jiayi Zhang, Chang Liu, Xijun Li, Hui-Ling Zhen, Mingxuan Yuan, Yawen Li, and Junchi Yan. A survey for solving mixed integer programming via machine learning. Neurocomputing, 519: 205-217, 2023.
Long Zhao and Bo Zeng. An exact algorithm for two-stage robust optimization with mixed integer recourse problems. submitted, available Oppimizaation-nnline org, 2012.
13

---

Published as a conference paper at ICLR 2024
A 2RO PROBLEMS
A. ROBUST TWO-STAGE KNAPSACK
We consider the two-stage knapsack problem as defined in Arslan Detienne 2022) with a set of n items. Each item has a weight c; and an uncertain profit Pi(E) Pt E.Pi, where Di is the expected profit, Ps its maximum deviation and & the uncertain profit degradation factor, where the degradation happens after the first stage. In this problem we have budgeted uncertainty set E = (5 E [0, 1 Σx= & S r]. The first stage decision is to choose subset of items to produce. Then in the second stage, there are three different responses to the profit degradation: (i) accept the degraded profit, (ii) repair the item by using an additional t, units from the budget to recover the original profit p., or (iii) outsource the item for cost of fa units, such that the item's 's profit results in P. ft. This gives the following problem formulation:
min max min xE(0,1)" EEe ye(0.1)".r(0.11"
E p.)ay + (P.E fi)s P.Car i=1
Σ cit + 1tri00 i=1 S
s.t.
Ti
y1 S x₁
E n..
where is the first-stage decision to produce item For the second-stage decisions, have y: and nyt (i) y/s = item is produced without repairing and y; = 0 the item is outsourced, and (ii) ry the decision for repairing item i.
A.2 CAPITAL BUDGETING
Consider the capital budgeting problem in Subramanyam et al. (2020), where company aims to invest in subset of projects. For each project, the uncertain cost, and profit are respectively defined as
(E) = (1+ and rE(E) (1 - VTE/2)rs. Vi (1.....,
where & and F; are the nominal cost and nominal profit of project i. o and V are the i-th row vectors of the sensitivity matrices o W R=x4 with & = = 1] We use the problem formulation described in
B 2RO ALGORITHMS
In this section, describe the column-and- and-constraint generation algorithm in more detail and the k-adaptability problem, briefly describing one of its solution methods.
B.1 COLUMM-AND-CONSSRAAA GENERATION
The CCG iterates between the main problem and the adversarial problem (AP). The MP is given as c(E) y
min max min EEB' yEy
(6a)
s.L. T(E)x (()) & h(E).
(6b)
where E' C finite subset of scenarios. Clearly, the MP provides lower bound the optimal To solve the MP, for each scenario in E' copy of the second-stage variables is
value of equation 2 generated. Using a level-set transformation, the problem can be formulated as
min xEX
(7a)
s.t.
cxE) + d(E)TTf S Aε E
(7b)
T(E)x + W(Ely E h(()
E
(7c)
" HE E 3A E
(7d)
14

---

Published as a conference paper at ICLR 2024
which is linear integer problem that state-of-the-art solvers, such Gurobi, can solve. In each iteration of the CCG an optimal solution (z", u²)) of equation is calculated. Afterwards, the AP is solved, which is defined as
max min EE= yEy
(6))x=+((E))
(8a)
s.t. W(EN h(g) - -(E))".
(8b)
Since the optimal value of the AP is the objective value of the current solution x", it provides an upper bound on the optimal value of equation 2 We define the optimal value to be equal to infinity if there exists scenario
E for which feasible second-stage solution exists. If the optimal value of the AP is larger than μI then we add the optimal scenario &* to E' and start again from solving MP. Otherwise, we stop the algorithm since the upper bound is smaller equal to the lower bound, and hence x" is an optimal solution. The whole procedure is presented in Algorithm [
Algorithm 1 Column -nndConsttrain Generation
ub 30, lb -0 E'= {&o } for any Eo E E while ub 1b 0 do
Calculate an optimal solution x², 4 of the main problem equation and set lb = μ². Calculate an optimal solution E (with optimal value opt") of the adversarial problem equa- tion 8 where = x².
Set U' and uh min (ub, opt*).
end while return x²
CCG often fails to calculate an optimal solution in a reasonable time since both the MP and the AP very hard to solve in the case of integer second-stage variables. In each iteration, the size of MP increases since we have to add new constraints and a copy of all integer second-stage decisions y. This often leads to the situation that after even small number of iterations, the MP cannot be solved to optimality anymore by classical integer optimization solvers as Gurobi.
Furthermore, solving the AP is extremely challenging for integer second-stage variables. Indeed, the problem can be formulated as bilevel problem where the follower problem contains integer algorithm that solves
variables. In Zhao & Zeng (2012) the authors present a doluum--nnd-onsterr the AP if the second-stage is a mixed-integer problem. One drawback is that this method is not ap- plicable the stage does not contain continuous variables, as the case for many problems, e.g., the capital budgeting problem. Furthermore, the method involves solving a very large mixed- integer bilinear problem, which is computationally enormously challenging. The whole procedure must be executed in each iteration of the main CCG algorithm.
B.2 --ADAPTABILITY
The k-adaptability approach was introduced in Bertsimas Caramanis (2010) and later studied for objective uncertainty and constraint uncertainty in Hanasusanto et al. (2015); Subramanyam et al.) ( et al. (2023); Julien al. (2022) y Kurtz (2023). The main idea of the approach is to calculate a set of k second-stage solutions already in the first-stage. Instead of choosing the best feasible second-stage solution for each scenario E. we choose the best of the calculated second- stage solutions. Since we restrict the number of second-stage reactions, this approach leads to feasi- ble solutions of equation 2 which are not necessarily optimal. While for larger the approximation guarantee gets provably better, the problem gets harder to solve at the same time. Furthermore, it was shown in |Subramanyam et al. (2020) that it may happen that & has to be chosen exponentially large to guarantee optimality for equation The k-adaptability problem can be formulated as
min max min EEB we (ut
(())x+d(EE))
(9a)
W(E) + T(E)x & h(g).
(9b)
15

---

Published as a conference paper at ICLR 2024
The k-adaptability problem is very challenging to solve, especially in the constraint uncertainty case. The best-known method for this case was introduced in (Subraaanya et al. (2020). The authors perform branch-and-bound algorithm over partitions of the uncertainty set. They consider k- partitions of finite scenarios sets, which are iteratively generated, and assign each of the second-stage solutions
later improved by applying machine learning methods to improve the branching decisions [Julien et al. (002)). As an alternative approach in Postek & Hertog (2016), an iterative uncertainty splitting method is presented, which converges to the exact optimal value of the two-stage robust problem.
of the partitions. This approach
In case of objective uncertainty, the k-adaptablity problem is easier (but still hard) to solve (Arslan et al. (2022): GGahtarani et al. (2023)) and can be approximated if k is not too small; see Kurtz 2023
C DETAILED FORMULATION
This section presents the detailed arg max formulation for equation 4 tion in the MP, we have scenarios f......fr & and that M and are upper and lower bounds on the prediction of the network. The complete formulation is then given by
We assume that at this itera-
min .EX.yEE....Sp....c..
Tx + d
(10a)
s.t.
W(aay + T(Ea)x S h(Ea),
(10b)
Pt = NNo(x, Ei)
Vi (1....,kk)
(10c)
u 2
vi E fl.....
(10d)
u S p: + (M L)(1 22)
vi (1.....k)
(10e)
k
Σ 2 =1
Vi (1....,k})
(10f)
i=1
&.
24
(10g)
1=1
To model the arg max, we introduce & binary variables z and k + continuous variables p and u, which are used to model big-M that ensure z at the index of the maximizer and 0 everywhere else. &a is then given by a linear combination of the scenarios multiplied with
D EXTENDED NN ARCHITECTURE
We show the extended neural network architecture used in the experiments in Figure
E
2RO WITH FIXED FIRST-STAGE DECISION
When we compare the calculated solutions of Neur2RO and the baseline in our experiments, we need to calculate the objective value of solution x* E X' exactly or approximately. The former involves solving the AP equation X for a given solution. Solving this problem is intractable when we have uncertain parameters in the constraints. We first expand on how the adversarial would be solved tractable way the uncertain parameters only appear in the objective function. Subsequently, describe an approach to approximately solve the AP, which is based sampling scenarios from
E. OBJECTIVE UNCERTAINTY
For the special of objective uncertainty, the AP can be solved much efficiently. In this case, the adversarial problem is given as
max min EEE yey
Tx + d
(11a)
s.t. Wy - h Txx,
(11b)
16

---

Published as a conference paper at ICLR 2024
Per First-Stuge/ Seenario Variable
Embodding Network
Pe
First-stage Embeddeing Network
2x
xx(xx))
Pa
Value dp Network
+ (concat( (x")), *c(("))
C
Scenario
as estimatc
Emaeddiing Network
cp
xx'
min 7
dr(E")yy
P
$c(
s.t.
Wo(e*)y s ho(e")) (x
Figure 3: The extended neural network architecture for ML-based CCG. Compared to the NN ar- chitecture shown in the main text (Figure 2), this model uses the set-based method to be able to generalize across instance sizes. Let E R and & E Ry Then, &x and & are the embedding networks for x; E [n] and { E [g]. respectively. The features comprised of the single vari- able and single-variable specific problem specifications Px [n] and P [q] for first-stage decisions and scenarios, respectively. The outputs of the & networks aggregated for x* and separately. These embeddings are the imput of the original NN given in the main part.
which can reformulated as
max EEE
@x
(12a)
s.t. a I c<E) + + Vy e D,
(12b)
where y = Ey: Wy < h Txx). While the D can contain exponential number of solutions, the latter problem can be solved by iteratively generating the constraints for E )
E.2 CONSTRAINT UNCERTAINTY
We collect all scenarios which were generated during training and during the solution proce- dures of the baseline algorithm and our algorithm (including the scenarios calculated by the AP) in the set ssamples Then for the two returned solutions x and x baseline we compare
max min @epeemples yEy
c(E)Tx* d
(13a)
s.t. W(E) < h(() T(E)x",
(13b)
where we replace x by the corresponding solution x* or baseline The latter problem can be solved by calculating the optimal value of the second-stage problem for each scenario independently and choosing the worst-case overall optimal values.
CONVERGENCE
In the following, present the proof of Theorem
Proof. The main idea is to show that the condition equation 5 cannot hold in infinitely many itera- tions. Since we stop the algorithm 5f is not true anymore, then finite termination of the algorithm follows.
Assume algorithm does not terminate a finite number of iterations. Let l, and r, be values of the left-hand side and right-hand side of inequality 5 in iteration / of the algorithm, i.e.
4 max N N EEE
and
= max N (x
Ee
17

---

Published as a conference paper at ICLR 2024
where x' is the optimal solution of MP in the t-th iteration and E' the finite set of scenarios used in the MP in iteration t. Let x E X be a feasible first-stage solution and let (x(x) and rx(x) be the sub- sequences which contain the values of 4 and r, only for the iterations where is an optimal solution of the MP. Then either this sequence is finite or, if it is infinite, the sequence {rr())}e monotonous and bounded where monotony follows since E E++1 and since the same is used. The sequence is bounded since E is bounded set and Ne piecewise-linear function (as known for feedforward ReLU networks (Montufar et 2014 and the maximum linear function over a bounded set is bounded. Hence, {ri(z) converges to a finite value r" (x). Furthermore, it holds 44 (x) I (x+1(x) since the optimal scenario of the sft-hand-side is added to E' which is a subset of the set later used to evaluate rx+ (x). It follows that
piecewise
T (x) S (xx) E (x+1(x) -E
for all which contradicts the convergence of (x). Hence the sequence ry (x) must be finite. Since only fimitely many first-stage solutions x exist, and the latter result holds for all of them, the number of iterations of the algorithm must be finite.
G DISTRIBUTIONAL RESULTS FOR RELATIVE PERFORMANCE
In this section, we provide distributional information for the RE for knapsack in Tables
3
and
Figures 8
Corellaiin Type
items
Mcan R.
Median RF
RF. 1st Quartile Neur2RO
RF 3rd Quartile
Neur2Ro
BP
Nauv2Ro
BP
BP
Neur2RO
BP
20
2,005
0.000
1.417
0.000
0.541
0.000
2,379
0.000
30
1.189
0.000
1.188
0.000
0.712
0.000
1,399
0.000
40
2,895
0.000
1.614
0.000
1.221
0.000
4,042
0.000
Uncomelated
50
3.032
0.000
1.814
0.000
0.946
0.000
3,801
0.000
60
2.099
0.000
0.577
70
2.214
0.000
1.408
0,010
0.761
0.000
2,506
0.000
80
0.000
0.758
0.000
0.000
20
2,569
0.000
1,582
0.000
1,229
0.000
4,010
0.000
30
2.664
0.000
2.236
0.000
0.616
0.000
4,293
0.000
Weakly Correlated
40
2.320
0.000
1.595
0,000
1.164
0.000
2,292
0.000
50
2,183
0.145
1.757
0,000
0.793
0.000
2.674
0.000
60
2.165
0.390
0.695
0.000
0.000
0.000
3.445
0,458
70
0,884
0.338
0.165
0.000
0.000
0.000
0.623
0.175
80
0.392
0.691
0.341
0.000
0.165
20
2.355
0.000
1.439
0.000
0.000
0.000
2.757
0.000
1.166
1,911
Almost Strongly
40
0,825
0.335
0.497
0,000
0.019
0.000
1.6066
0.000
50
0.314
0.884
0.019
0.000
0.000
0.000
0.229
1.25
Correlated
60
0.197
0.523
0.000
0.016
0.000
0.000
0,268
1.129
70
0.551
0.615
0.017
0.031
0.000
0.000
1,058
1.227
80
0,188
0.694
0.265
0.000
20
2,387
0.000
1.604
0.000
0.905
0.000
3.018
0.000
30
0.000
0.054
Strongly
40
0.658
0.191
0.443
0,000
0.002
0.000
0.888
0.000
50
0,411
0.000
0.000
0.000
0,780
0.963
Correlated
60
0.322
0.367
0.042
0.010
0.000
0.000
0.173
0.693
70
0.389
0.738
0.020
0.027
0.000
0.000
0.535
0.793
80
0.318
0.668
0.000
0.179
0.000
0.000
0.245
0.906
Table 3: Table of distributional information for knapsack. For each row, all RE statistics are com- puted over 18 instances.
licms
Moxn 2
Maiian
RE Quantile
Quartile
2ito:20t
2ito
J=
k-5
2.558
1.105
0,000
3.534
0.423
0.232
0,000
0.112
0.410
0.330
0.408
0.109
0.212
0.090
0.050
0:190
Table 4: Table of distributional information for capital budgeting. For each row, all RE statisties are computed over 50 instances.
18

---

Published as a conference paper at ICLR 2024
Neu
BP
0
50
60
70
80
Items
Figure 4: Boxplot of RE for baseline and 2eur on UN knapsack instances.
10
Neuz
BP
6-
2-
0
20
70
80
Items
Figure Boxplot RE baseline and Neur on WC knapsack instances.
2eu
6'
4:
2:
000
0:
20
30
60
70
80
Items
Figure 6: Boxplot of RE for baseline and Neur2RO on ASC knapsack instances.
H ABLATION
This section presents an ablation across aspects of Neur2RO, namely, the formulation of the MP and the method to obtain worst-case scenarios. Both results are presented on the knapsack instances.
H. MAIN PROBLEM FORMULATION
As an alternative to the formulation using arg max over set of scenarios. One more straightforward formulation consider instead the max over all of the scenarios, which is given by
19

---

Published as a conference paper at ICLR 2024
Neur
BP
8
4
2:
00
0:
20
30
40
50
60
70
80
# Items
Figure 7: Boxplot of RE for baseline and Neur2RO SC knapsack instances.
17.5
8
Meur2RD
3.5
Meur2RD
15.0
2
3.0
2.5
12.5
8
10
10.0
2.0
7.5
1.5
5.0
2.5
0.5
8
0.0
0.0
10
20
30
Iteens
Items
Figure 8: Box plot of RE for baselines and Neur2RO on capital budgeting instances.
min xEA
Q
(14a)
s.t. 22 N2NNNo
Wk E (1...,,KK K}.
(14b)
Table reports the MRE of the arg max and max formulations and the solving time. Table demonstrates an improvement in solution quality, with arg max obtaining lower MRE in every case and a lower computing time in most cases.
H.2 WORST-CASE SCENARIO ACQUISITION
This section compares the adversarial approach for determining scenarios sampling and linear programming (LP) relaxation-ba based approach.
H.2.1 LAMPLING-BASER SCENARIO ACQUISITION
For sampling, baseline, we sample 100, 000 scenarios, and then approximate the AP, we take the maximizer over a forward pass. demonnsteess a clear trade-off between solution quality and efficiency. Generally, sampling improves average solving time across all instances but leads to worse solution quality as the instance size increases.
H.2.2 LP RELAXATION BAASDD SCENARIO ACQUISITION
For 2RO, the uncertainty set often polyhedral, which scenarios can be heuristically obtained via LP relaxation. For the LP relaxation, compare the performance of the standard MILP-base based scenario acquisition (standard), i.c., solving the AP to optimality, to the relaxation (LP relaxation). For both problems, report the RE to the baselines. Tables and g present the knapsack and
20

---

Published as a conference paper at ICLR 2024
Correlation Type
# items
Median RE
Times
arg juxx
mux
ang LIx
20
0.000
1.167
5
11
30
0.000
0.945
7
0.000
Uncorvelated
50
0.000
1.634
10
33
70
0,000
0,801
19
28
0.000
2.227
0.000
3.515
30
0,000
2,405
11
22
Weakly
0.000
0.502
Correlated
50
0.000
0,254
60
0.000
1.528
77
80
0.000
3,492
27
75
0.000
2.042
0.000
Almost
40
0.000
1.739
11
33
Strongly
Correlated
60
0.000
2,449
1S
30
0.0000
2.497
0.000
1.824
20
0.100
1.154
S
11
0.000
0.967
7
Strongly Correlated
0.1K10
1.928
50
0.000
3.613
21
0.000
2,005
70
0.000
2.657
16
33
0.000
2.051
Table 5: arg max and max formulations on knapsack instances. For each row, the median RE and solving time are computed over 18 instances. All times in seconds.
capital budgeting results, respectively. In general, we can observe that the LP relaxation leads to significantly faster solving time, with an overall decreased solution quality. That being said, for capital budgeting in particular, Neur2RO with the LP relaxation still achieves a lower median RE than the baselines on larger instances, while being roughly five times faster than results without the relaxation.
H.3 PREDICTION TARGET
This section compares the prediction target. For capital budgeting, the coefficients of the first-stage
decisions in the objective contain uncertainty. As such, this presents choice of either predicting the
sum of the first- and second-stage objectives, i.e., c(E) minyey {d(+) W h(E)
x(E)x). J. or only the second-stage objective, i.e., minyyey {d(E) : W S h({) - T()))) Specifically, we compare the downstream optimization performance with respect to the resulting formulations. The formulation for predicting the sum of the first- and second-stage objectives is presented in Section
3
For predicting the second-stage objective only, the MP is given by
min xEX.EEEE
c(Ea) + d(E.)Ty
(15a)
s.t. W(E.)y + T(Ea)x < h(Ea),
(15b)
Ea E arg (c(E) NNe {)}
(15c)
and the AP given by
max (()) NNo(x" EEE
(16)
The main difference with this formulation is that the objective coefficients c(E) can be utilized di- rectly rather than requiring the ML model to predict them. compares the two approaches on the capital budgeting instances wherein the RE is computed with respect to the baselines. Empiri- cally, we can see that predicting the sum of the first- and second-stage objectives yields significantly better solutions. On the methodological side, when only the second stage is predicted each node in the branch-and aanechh-nd-buuudd boud- tree being explored by a MIP solver will contain the exact first-stage and the predicted second-stage objectives. As such, speculate that the IP relaxation at each node will
21

---

Published as a conference paper at ICLR 2024
Correlation Type
# items
Median RE
Times
sampling
adversarial
sampling
0.000
0.000
30
0,000
0.000
0.560
0.000
Uncorrelated
0.723
0.000
10
60
0.066
0,000
17
0.150
0.000
19
0.395
0.000
13
0,000
0.074
30
0,000
0.444
11
Weakly
0.000
26
Correlated
50
0.441
0.000
24
60
0.119
0.065
77
0.000
80
0,000
0.536
27
20
0,000
0,000
0,000
0.000
Almost
0.000
0.000
11
Strongly
50
0,000
0,000
7
Correlated
0,000
0.000
15
0,000
0.000
18
13
80
0.000
0,000
17
12
0,000
0,000
0.000
0.000
Strongly Correlated
40
0,000
0,000
16
11
0,000
0.000
10
8
20
70
0,000
0.000
16
14
0.000
0.000
16
Table 6: Adversarial and sampling-base based approaches for worst-case scenario acquisition on knap- sack instances. For each row, the median RE and solving time computed over 50 instances. All times in seconds.
Cumelation
items
Median RE
Times
Corrlation
stems
Medhan RE
Times
Type
standard
L. rilatationn
standand
LP relactaiion
Type
standard
I.P relasation
stanaadd
I.P velosstioon
30
1.167
30
0.742
0.665
1.357
Almost
Oncorrelated
Stummly
Correlaned
1.079
1,38
30
2,034
11
30
0.610
0.796
Weakly
Conelated
50
60
40
B.695
1.757
0.729
1.126
77
20
19
Sunagly Canelated
50
60
0.073
0.042
0.500
2.333
1,375
11
70
0.165
0.341
15
70
8J020
01623
16
50
0,000
0.316
21
80
0
1.097
13
Table Median RE and solving times for knapsack instances with LP relaxation. For each row, the median RE and average solving time are computed over 18 instances. All times in seconds. The smallest (best) values in each row/metric are in bold.
consist of two components that entirely different scales. Specifically, the first-stage objective will be tight as it is being represented exactly while the second-stage objective requires the relax- ation of the prediction model which will be tight due the big-M constraints. This means that the maximization problem in the AP favors the second stage. This mismatch could lead to inaccurate scenarios and undesirable downstream effects within
H.4 BASELINE SOLUTION QUALITY NEUR2RO TERMINATION TIME
In this section, we report the objective quality, i.c. the median relative error, for k-adaptability that the
baseline the termination time of Neur2RO in Table IO From the table,
performance is median RE of Neur2RO is marginally better than when k-adaptability given hours, except 20, 40. Note that these tables are only be reproduced for capital budgeting
22

---

Published as a conference paper at ICLR 2024
# items
Median RE
Times
standard
LP relaxation
standard
LP relaxation
10
1.105
2.663
59
4
20
0.000
0.060
324
142
30
0.109
0.071
602
141
0.009
0.007
739
226
0.001
0.001
1,032
Table 8: Median RE and solving times for capital budgeting instances with LP relaxation. For each row, the median RE and average solving time computed over 50 instances, All times in seconds. The smallest (best) values in each row/metric are in bold.
# items
Median RE second only
Times
sum
sum
second-only
10
1.105
2.424
20
233
20
0.000
0.192
324
1,823
30
0.109
0.151
602
3,823
40
0.009
0.010
739
4,062
50
0.001
0.005
1,032
7,424
Table 9: Sum and second-stage only predictions for capital budgeting instances. For each row, the median RE and solving time are computed over 50 instances. Note that in these results, the RE calculated with respect the k-adaptability and each respective ML-approach. All times in seconds.
we do not have the knapsack results throughout the solving process, given only the final objective values are reported in Arslan Detienne (2022).
# items
Median RE at hours
Median RE al Neur feur2RO RO termination
Neur2RO
k = 2
k 5
k 10
Neur2RO
k == 2
k ==
h = 10
10
1.105
1.140
0.000
0.000
0.809
1.559
0.267
0.359
20
0.000
0.196
0.112
0.064
0.011
0.240
0.098
0.084
30
0.109
0.020
0.073
0.032
0.102
0.067
0.093
0.029
40
0.009
0.074
0.011
0.019
0.013
0.079
0.058
0.019
0.001
0.033
0.039
0.020
0.002
0.035
0.006
0.008
Table 10: Median RE for capital budgeting at 3 hour time limit and Neur2RO termination time. For each row, the median RE and average solving time are computed over 50 instances. All times in seconds. The smallest (best) values in each row/metric are in bold.
MACHINE LEARNING MODEL DETAILS
I.1 FEATURES
Here we provide the features for each of the problems. both cases, set-based architectures Zaheer et al. (2017) with parameter sharing utilized, so we report the features for single dimension of the lirst-stage decision and scenario accordingly. Table [T reports all of the features for each instance.
1.2 MODEL HYPERPARAMETERS
This section reports the hyperparameters for the neural networks for each problem. For both prob- lems, have the same architecture with slightly different hyperparameters. As the objective of Neur2RO is to enable efficient optimization, we train small networks that can achieve a low mean absolute eиror value to ensure that the main and adversarial problems tractable. For this reason, no systematic hyperparameter tuning was done. Hyperparameter optimization would likely only further improve the already strong numerical results. For both problems, we train model for 500
23

---

Published as a conference paper at ICLR 2024
Problem
First-Stage Features
Scenario Features
Knapsack
Te (t.Ps,Ps, Fs, t4. C
&,, ft. C + 22222), (1 v.622), C
Capital budgeting
3i, Ni,
Table 1 1: Features for first-stage decision and scenario embedding networks.
epochs and compute the mean absolute model with the lowest reported mean absolute validation error during training for evaluation.
validation every 10 epochs. We then the
Table 12 reports the hyperparameters for each model. As our model generalizes across instances, which requires invariance to the order and number of decision variables, both the first-stage and sce- nario embedding networks are set-based architectures (Zaheer et al., 2017). We refer to Figure for a refresher on the overall architecture which has the following hyperparameters. The hyperparame- ters " dimensions" and "Øx dimensions" correspond to the hidden and embedding dimensions of the first-stage embedding network. Specifically, "Øx dimensions" corresponds to the network with shared parameters that embed the representation for each first-stage decision. The last dimension of "Øx dimensions" is that of the aggregated vector. The hyperparameter "Øx dimensions" cor- responds to the network that takes the aggregated first-stage embedding vector input. The last dimension of " dimensions" specifies the embedding dimension of the first-stage embedding net- work. "he dimensions" and "the dimensions" are analogous for the scenario embedding network. "& dimensions" correspond to the hidden dimensions of the value network. Finally, "aggregation type" specifies the type of aggregation that combines the first-stage/scenari embeddings.
Hyperparameter
Knapsack
Capital budgeting
Feature scaling
min-max min-max
min-max
Label scaling
min-max
# epochs
500
500
Batch size
256
256
Learning rate
0.001
0.001
Dropout
Loss function
MSELoss
MSELoss
Optimizer
Adam
Adam
dx dimensions
[32, 16]
[16, 4]
4x dimensions
[64, 8]
[32, 8]
t dimensions
[32. 16]
[16, 4]
g dimensions
[64, 8]
[32, 8]
dimensions
[8]
[8]
Aggregation type
sum
Table 12: Hyperparameters for neural networks.
1.3 TRAINING CURVES
Figures 9
I0 plot the mean absolute error every 10 epochs during training for the training and validation data. Generally, the training and validation mean absolute error is very close, and both problems, relatively low mean absolute error is achieved.
24

---

Published as a conference paper at ICLR 2024
0.012
Train
Mean absoluts error
Validation
0.010
0.008
0.006
0.004
100
200
300
Epoch
Figure Training curve for knapsack.
0.0550
Train
Mean absolute error
0.0525
Validation
0.0500
0.0475
0.0450
0.0425
0.0400
0.0375
0.0350
100
200
300
400
500
Epoch
Figure 10: Training curve for capital budgeting.
25


Reviews:
[{"review_id": "xHhhfnB6bl", "reviewer": "Reviewer_3Yd3", "summary": "The authors study the problem of solving robust mixed integer programming problems using deep learning. As a main contribution, deep neural networks (DNN) are used as a building block to accelerate existing column and constraint generation algorithms. To be specific, the DNN model is first used to learn a mapping from input to the objective value of the stage-2 problem. Then, the trained DNN is embeded into the original robust optimization problem based on its mixed integer linear programming formulation. Simulations on over several cases are conducted to show the effectiveness of the proposed approach.", "questions": "1. The contribution of the paper is not clear. In [R1], deep neural network (DNN) is used to solve the stochastic mixed integer programming problem. The key idea is to use DNN to learn the input to objective value mapping of the stage-2 problem. Then, the DNN model is embeded into the original stochastic programming problem as a mixed integer programming formulation. The idea of the paper is similar to that in [R1]. The authors are suggested to explain the key differecens the these two papers and show the contribution of the paper clearly. \n\n2. In paragraph 4 of Sec. 3.2, the authors mention \"Prediction inaccuracy is then compensated for in equation 4a by exactly modeling the second-stage cost. As a result, when solving the MP, the true optimal first-stage decision for the selected scenario will be the minimizer, rather than a potentially suboptimal first-stage decision based on any inaccuracy of the learning model.\" This is not easy to follow. The authors are suggested to express it more clearly.\n\n3. To accelerat the column and constraint genration algorithm using DNN, one straightforward approach is using DNN to predict the worst-scenario for the stage-2 problem and then add the obtained scenario to the main problem. The authors are suggested to explain why this straightforwrd design will not work. Otherwise, the authors are suggested to use this straightfoward design as a baseline approach to show the superiority of the proposed approach. \n\n4. The authors are suggested to use more real-world problem as the case study. For example, the robust unit commitment problem in power system operation.\n\n5. The authors are suggested to analyze the impact of the DNN prediction errors to the performance (such as convergence and optimality gap) of the proposed approach.\n\n\n\n[R1] Patel, R.M., Dumouchelle, J., Khalil, E. and Bodur, M., 2022. Neur2SP: Neural Two-Stage Stochastic Programming. Advances in Neural Information Processing Systems, 35, pp.23992-24005.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The topic of the paper is interesting.\n2. The paper proposes a new deep learning approach to solve the robust mixed integer programming problems.\n3. The paper is easy to follow.", "weaknesses": "1. The contribution of the paper is not clear. See the comments below.\n\n2. The simulations are not sufficient. See the comments below.", "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": "", "extra_scores": {}}, {"review_id": "rH51vEuhd8", "reviewer": "Reviewer_viyN", "summary": "In this paper the authors combine machine learning and optimization to develop an algorithm to solve two stage robust optimization problems in a more efficient fashion. They do so by modifying the column and constraint generation algorithm for two stage RO problems. \n\nThey train a Neural Network which predicts the optimal value of the second stage problem given the first stage decisions and the uncertainty realizations and incorporate the NN into the mathematical programming problems used to compute the initial decision and uncertainty realizations.\n \nThis allows for faster and better computation of the first stage decisions and the worst case realizations. \nThey also show that their algorithm will terminate after a finite number of steps if the initial feasible region is finite. \n\nThey numerically illustrate their results on a Knapsack and a capital budgeting problem.", "questions": "1. How much of an impact does the complexity of the Neural Network have on solution time vs relative error. \n2. Did you evaluate the approach on any non binary problems. How was the performance on them. \n3. Did both the knapsack and the budgeting problems involve only one constraint? Did you try the approach on problems with more constraints?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "**originality**: The use of neural networks to predict value functions is quite commmon especially in reinforcement learning literature. However, the incorporation of the neural network into a standard mathematical programming problem is new. \n\n**quality**: The algorithm developed is justified theoretically and works well on the problems under consideration. \n\n**clarity**: The paper is well written and presents its arguments well. The experiments are clear and succinct. \n\n**significance**: This approach presents a new approach which can be used to solve challenging two stage constrained robust optimization problem while still maintaining optimality guarantees.", "weaknesses": "The applications considered are quite limited and don't really give an idea of how the approach will work in problems with other constraints beyond just the packing constraint.", "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": "", "extra_scores": {}}, {"review_id": "BV4HPUG9TA", "reviewer": "Reviewer_fXRT", "summary": "The authors propose an approach for solving two stage robust optimization that empirically solves previously intractable problems. The setting considers optimization problems where a set of initial decisions are made, and then a worst-case setting is evaluated and in that worst-case setting the decision-maker can make second-stage decisions to react and ideally improve their deployment. Here the first stage solutions are evaluated based on how robust they are to adversarial settings considering that the decision-maker can react in a pre-specified manner. As this problem considers the nesting of 3 optimization problems it’s empirically very difficult to solve. The standard method here is to maintain a main problem, and then add worst-case scenarios modeling them as cutting planes. The issue here is that due to the inherent multi-level optimization problem, these problems are intractable. The proposed approach is to approximate the value of the lower-level problem in each of these settings using a neural network and then embed the neural network in the outer optimization formulation. Here the neural network is trained to take in a first stage decision as well as a setting and output a value estimating the quality of the best possible second stage recourse given the first stage solution and setting. As such, finding the worst-case adversarial setting amounts to optimizing the output of the neural network value estimator, and finding an estimate of the best possible first-stage solution amounts to optimizing over all possible settings, the output of the neural network estimator. They demonstrate performance on a robust two stage knapsack setting and a capital budgeting setting, demonstrating that their approach can give high-quality solutions in tens of seconds which aren’t solvable by previous methods in 3 hours. The approach demonstrates scalability, and the authors also prove convergence guarantees demonstrating that the algorithm is guaranteed to converge in finite settings.", "questions": "It may be helpful to define what the “adversarial problem” is versus the “second stage problem” (and the corresponding second stage value function). It seems that the adversarial problem is the minimization over xi. Is the second stage problem the optimization over y?\n\nAre the samples used for training randomly drawn before any solving happens? Are those samples representative of the settings in which the optimization will be occurring over? For instance, the optimization may be performed over a very different part of the feasible space than what was used for sampling. It would be interesting to see a measure of accuracy for the learned models over time at different stages of the solving process.\n\nWhat does the solving performance look like over time? The solution qualities are somewhat similar whereas the runtimes are drastically different. Is it the case that the baseline very quickly jumps to high quality solutions and stays there? Or does it continue to improve gradually. You might consider evaluating a form of primal integral measuring the performance of the first stage solutions over time. As a quick solution, you might also consider evaluating the solution quality at around the same time it takes the Neur2RO model to terminate.\n\nIt would help to have notions of error on the statistics since some of the relative errors are somewhat close.\n\n\nSmall comments:\nP6, experimental setup 2RO Problems\nAs larger or larger -> as large or larger", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The core strengths are the drastically improved performance over previous approaches and well-motivated approach. ¬\nThe improved performance means that problems that were previously intractable are now heuristically solved in tens of seconds, enabling the use of two stage robust optimization for larger or more complex problem settings. \nAdditionally, the approach itself is well-motivated by approaches in the optimization literature. By embedding a neural network in the subproblem solver as well as the top-level solver they ensure that the deployed solution is guaranteed to satisfy the constraints and be robust to the enumerated settings. Furthermore, by working with an exact solver, and using the true objective function, the authors guarantee that the resulting objective value of the top-level problem is an objective value corresponding to the first-stage solution for an actual setting.", "weaknesses": "The main weakness is that the scope of impact is somewhat limited to two stage robust optimization. It might be helpful to expand somewhat on where this approach might be useful by giving some examples that are two stage robust optimization from the cited survey on adjustable robust optimization. Alternatively, it might be helpful to give some examples on ways that this can be readily extended to cover more flexible problems such as general-purpose multi-level solver.\n\nAdditionally, it is not the first use case of embedding neural networks in optimization to solve hard optimization problems as this was previous done in the cited Dumouchelle 2022 paper. However, this is certainly not a direct extension of that work as the neural network is embedded both in the subproblem as well as the main problem in a manner that is cohesive with the optimization formulation to ensure convergence guarantees and which mimics the original solver.\n\nOne slight weakness might be that there are limited baselines. However, it should be noted that there are not many general-purpose solvers in these settings. Would it be possible to compare against a naïve extension of Dumouchelle 2022? It might be possible to train a neural network to take in as input only first stage decisions and output the value of all subsequent decisions. It might be computationally expensive to create a training dataset as one would have to evaluate first stage solutions; however, it may be possible. It seems that might be more difficult for a neural network to model, but potentially give a heuristic solution with one solver call.\n\nAnother slight weakness is that there are not many settings evaluated outside of two knapsack-like settings. It might be helpful to demonstrate this approach on other two stage robust optimization settings with potentially more complex feasible regions that would potentially be more difficult for the neural network to model.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)