Neur2RO: Neural Two-Stage Robust Optimization

Thank you for the detailed comments. We will first comment on a couple of the weaknesses mentioned to provide more insight from our perspective.

• Firstly, regarding the use of predicting the value function using only the first-stage decision. We have thought about this as well, but in general came to similar limitations as you mentioned above.
  • As you noted, data collection will be expensive. In fact, obtaining the regression target (the objective of the inner max/min) requires solving a bilevel optimization problem with integer follower decisions (at least for problems with constraint uncertainty, e.g., capital budgeting), so this may be prohibitively expensive, and will likely be much less scalable to larger instances and other more challenging 2RO problems.
  • We also agree that it will likely be more difficult to model the max-min function based on the first-stage decision alone. This difficulty may be even more significant when training across instances with varying sizes, objectives, and feasible regions, as explored in this work, but not [Dumouchelle, 2022].
• Regarding the benchmarks, both problems indeed involve similar knapsack-like constraints. Our method would, in theory, be capable of handling more than this, as we predict the second-stage objective with respect to its constraints. We are currently working on an extension of this work that addresses problems with more challenging constraints, namely, a facility location problem. Our first tests indicate that a similar performance boost is possible as shown in the paper. However, due to the limited time we cannot provide these new computational results in this submission. These additional results will be included in the final version of the paper if accepted, space permitting.

Next, we will address the questions.

1. The second-stage problem is purely an optimization over the second-stage variables $y$, where $x$ and the scenarios are fixed (see Equation 3 from the paper). The adversarial problem is the $\max_\xi \min_y$ problem, which is a bilevel integer optimization problem (see Figure 1, box(c) from the paper, or Equation 8 from the supplementary material).
2. The samples are indeed drawn randomly over the entire uncertainty set. We have discussed this issue among ourselves, and we have conducted some small experiments along the lines you proposed.
   • Specifically, we compare the predicted objective (i.e., the max of the NNs) to the actual objective in the main problem. For strongly correlated knapsack with $n=20$ and $80$, the MAE is $0.021$ and $0.034$, respectively. For capital budgeting with $n=10$ and $50$, the MAE is $0.173$ and $0.184$, respectively. Generally, these results are at most one order of magnitude worse than the MAE reported during training.
   • In our opinion, this further justifies the use of argmax as misprediction in the main problem can be mitigated.
   • It also motivates that if more time is spent on finding worst-case scenarios, either during data collection or using scenarios found during solving to retrain, this would likely only improve the already strong numerical results we have.
3. To give more insight into the solving process, see the points below:
   • Generally, the baselines (k-adaptability) will find decent but worse solutions somewhat early in the solving process and slowly improve over time.
   • We have added the table comparing the solution quality at ML termination time to the supplementary materials in Table 8. From the table, we can see that the performance is slightly better at the time of ML termination, but not always, i.e., for $n=20$ median relative at ML time, it is slightly worse.
   • We would also like to mention that these are the updated results for capital budgeting, for which the improvement over the baseline is more significant for our method.
   • We agree that comparing primal integrals over time would be a valuable performance measure and will be considered for future extensions of this work.
4. See Tables 4-5 and Figures 4-8 in the supplementary materials for statistics and box plots of the relative error.

Thank you for the review, we will provide answer to the questions in this comment.

1. We did not compare this systematically. However, generally, we observed that decreasing the capacity significantly resulted in a training/validation error that was significantly larger, whereas increasing capacity did not significantly improve the error. In general, larger NNs are more challenging to optimize over in the MILP, as it requires more variables and constraints so that we would expect a significant increase in solution time. In future work, we will aim to address this in more detail.

2. The main focus of this work is on two-stage robust optimization (2RO) problems with discrete recourse. As we have mainly focused on benchmark instances from the 2RO literature, most of these include only binary decisions. We note that there is nothing limiting our approach to the binary case, so we agree this would be an interesting comparison.

3. Both problems do indeed involve one (non-trivial) constraint. Our method would in theory be capable of handling more than this, as we predict the second-stage objective with respect to its constraints. We are currently working on an extension of this work that addresses problems with more challenging constraints, namely, the facility location problem.

We will address the first two questions in this comment.

1. Firstly, we do acknowledge that the learning of the value function for the second-stage problem is shared. However, the domains in which the papers focus, i.e., two-stage stochastic programming (2SP) and two-stage robust optimization (2RO), differ substantially and require specific contributions to the case of 2RO. Below, we summarize the important differences and contributions.

   • Architecture: In [R1], a major contribution is made by architecture, which leads to efficient optimization by learning to aggregate scenarios. In 2RO, aggregation of scenario information, especially before the first-stage decision is input to the model as in [R1], is not ideal, as the worst-case scenario directly depends on the first-stage decision. As such, 2RO essentially requires a learning model that predicts based on a single scenario. While this can be done with a standard feed-forward style architecture, such as the per-scenario architecture in [R1], this will suffer from the same scalability issues as demonstrated in [R1] as optimizing over an entire neural network for each scenario will quickly become intractable as the number of scenarios increases in the main problem (MP). This highlights the main contribution of the architecture in our paper, which enables efficient optimization in the MP for 2RO via only embedding the Value Network for each scenario.
   • Generalization: One major limitation of [R1] is that the learning models were trained and evaluated on the same instance with varying scenarios, whereas, in this paper, we propose an architecture that can generalize across families of instances representing coefficients of the optimization problems as features, and applying set-based architectures.
   • NN approximations within an iterative algorithm: One major distinction between [R1] and this work is how the NN-based approximations are utilized. In the 2SP setting, [R1] use NN-based value function approximation to directly approximate the extensive form, which results in a single-level optimization problem. To the best of our knowledge, our work is the first to address NN-based value function approximation within the context of an iterative algorithm for mathematical optimization.
   • The argmax formulation: As demonstrated in our supplementary results, the obvious choice of using a max over the NN predictions, which would be equivalent to the expectation in the per-scenario approximation of [R1], results in strictly worse performance. This argmax formulation for the MP provides an alternative (and completely new) way to approach the CCG main problem by leveraging the actual coefficients of the underlying optimization problem, rather than purely relying on the predictive model. While this exact formulation may be limited to 2RO, we suspect the general idea, utilizing predictions in conjunction with true parameters of the optimization model, may have extensions within various ML-based algorithms for other mathematical optimization settings.

2. We will clarify this in detail in the final version of the paper and provide a clearer explanation here.

   • Firstly, the naive usage of the prediction model in the MILP formulation would be to use the output of the predictive model directly in the objective. This would be similar to the per-scenario approximation in [R1] wherein the average of predictions is used. A maximum over the predictions w.r.t. different scenarios would then be taken in the 2RO case. This formulation, which we will refer to as max-MP, is detailed in Equation 14 of the supplementary material. We refer to the formulation using argmax (Equation 4 in the main paper) as the argmax-MP.
   • Consider the case where both the max-MP and argmax-MP formulations identify the same worst-case scenario, $\xi$. From this, we know that if $x^\star$ is the minimizer for a particular scenario in the true MP, then the optimal first-stage decision for the argmax-MP will be $x^\star$ as their objectives are identical. However, for the max-MP formulation, it may be the case that there exists some $\hat{x}$, such that $c(\xi) ^\intercal \hat{x} + NN(\hat{x}, \xi) < c(\xi)^\intercal x^\star + NN(x^\star, \xi)$. So in this case, misestimation may in fact lead to a suboptimal first-stage decision in the max-MP formulation.